218 - Moth Eradication

snar · Post by **snar** » Sat May 13, 2006 8:52 pm

Thanks,
I'll try them too, when i'll have a time.

snar · Post by **snar** » Sun May 14, 2006 6:54 pm

Got it!

My algorithm was building a Convex Hull with minimal number of vertices. I've changed it to maximum ( including colliear points too ) and got Accepted.

Thanks everyone,

Moha · Post by **Moha** » Mon May 15, 2006 1:45 pm

Yes, as the problem statement says that.

Shuvra(CSE-BUET) · Post by **Shuvra(CSE-BUET)** » Fri Sep 01, 2006 11:15 pm

I am very much astonished why I get WA always. I also checked every input from other threads. Now I am posting only my main fn here.
Pls tell me what is wrong?My graham scan function is 100% OK and I got acc in other programs. It sorts in ccwise . So I print from backward.
After convex hull I insert points in result with hull points correctly.
..........................................................................................................
void main(){

int n,i,j,k,l,m,kstart,kend;
point temp;
double dis;
long int reg=1;
while(scanf("%d",&n)==1 &&n!=0 ){
for(i=0;i<n;i++)
scanf("%lf%lf",&in.x,&in.y);

convex_hull(in,n,hull);
copy_point(hull.p[0],hull.p[n]);
k=0;
if(n>3){
for(i=0;i<hull.n;i++)
{
copy_point(hull.p,result.p[k]);
k++;

for(j=0;j<n;j++)
{

if( !compare(hull.p,in[j]) && !compare(hull.p[i+1],in[j]) && collinear(hull.p,hull.p[i+1],in[j]) )
{

if(i+1!=hull.n){
copy_point(in[j],result.p[k]);
k++;
}//if
else{
kstart=k;

for(;j<n;j++)
{
if(!compare(hull.p,in[j]) && !compare(hull.p[i+1],in[j]) && collinear(hull.p,hull.p[i+1],in[j]) )
{
copy_point(in[j],result.p[k]);
k++;
}//if
}//for
kend=k-1;
for(l=kstart,m=kend;l<m;l++,m--)
{
copy_point(result.p[l],temp);
copy_point(result.p[m],result.p[l]);
copy_point(temp,result.p[m]);

}
break;
}//else
}//if

}//for
}//for
}
dis=0.0;
n=k;
if(k==0)
{
n=hull.n;
}
if(n<=3){
for(i=0;i<n;i++)
copy_point(hull.p,result.p);
}
copy_point(result.p[0],result.p[n]);

for(i=0;i<n;i++)
{
dis+=distance(result.p,result.p[i+1]);
}
if(reg!=1)
printf("\n\n");
printf("Region #%ld:\n",reg);
reg++;
if(n==3){

if(!ccw(result.p[0],result.p[1],result.p[2]) && ! collinear(result.p[0],result.p[1],result.p[2]) )
{
copy_point(result.p[1],temp);
copy_point(result.p[2],result.p[1]);
copy_point(temp,result.p[2]);
}
else if(collinear(result.p[0],result.p[1],result.p[2]))
{
if( fabs(distance(result.p[0],result.p[2]) - distance(result.p[0],result.p[1]) -distance(result.p[1],result.p[2])>EPSILON) )
{

copy_point(result.p[1],temp);
copy_point(result.p[2],result.p[1]);
copy_point(temp,result.p[2]);

}
}

}
printf("(%.1lf,%.1lf)",result.p[0].x,result.p[0].y);
if(n==3 && collinear(result.p[0],result.p[1],result.p[2])){
for(i=1;i<=2;i++)
printf("-(%.1lf,%.1lf)",result.p[i].x,result.p[i].y);
for(i=1;i<=1;i++)
printf("-(%.1lf,%.1lf)",result.p[i].x,result.p[i].y);
printf("(%.1lf,%.1lf)",result.p[0].x,result.p[0].y);
}
else{
for(i=n-1;i>=0;i--)
{
printf("-(%.1lf,%.1lf)",result.p[i].x,result.p[i].y);
}
}
printf("\nPerimeter length = %.2lf",dis);

}
}

CodeMaker · Post by **CodeMaker** » Sat Sep 02, 2006 6:48 am

Here is some I/O from my AC programe.
BTW, these are auto generated.

INPUT:

Code: Select all

41
18.467000 6.334000
26.500000 19.169000
15.724000 11.478000
29.358000 26.962000
24.464000 5.705000
28.145000 23.281000
16.827000 9.961000
0.491000 2.995000
11.942000 4.827000
5.436000 32.391000
14.604000 3.902000
0.153000 0.292000
12.382000 17.421000
18.716000 19.718000
19.895000 5.447000
21.726000 14.771000
11.538000 1.869000
19.912000 25.667000
26.299000 17.035000
9.894000 28.703000
23.811000 31.322000
30.333000 17.673000
4.664000 15.141000
7.711000 28.253000
6.868000 25.547000
27.644000 32.662000
32.757000 20.037000
12.859000 8.723000
9.741000 27.529000
0.778000 12.316000
3.035000 22.190000
1.842000 0.288000
30.106000 9.040000
8.942000 19.264000
22.648000 27.446000
23.805000 15.890000
6.729000 24.370000
15.350000 15.006000
31.101000 24.393000
3.548000 19.629000
12.623000 24.084000
4
18.756000 11.840000
4.966000 7.376000
13.931000 26.308000
16.944000 32.439000
26
11.323000 5.537000
21.538000 16.118000
2.082000 22.929000
16.541000 4.833000
31.115000 4.639000
29.658000 22.704000
9.930000 13.977000
2.306000 31.673000
22.386000 5.021000
28.745000 26.924000
19.072000 6.270000
5.829000 26.777000
15.573000 5.097000
16.512000 23.986000
13.290000 9.161000
18.636000 22.355000
24.767000 23.655000
15.574000 4.031000
12.052000 27.350000
1.150000 16.941000
21.724000 13.966000
3.430000 31.107000
30.191000 18.007000
11.337000 15.457000
12.287000 27.753000
10.383000 14.945000
9
32.209000 9.758000
24.221000 18.588000
6.422000 24.946000
27.506000 13.030000
16.413000 29.168000
0.900000 32.591000
18.762000 1.655000
17.410000 6.359000
27.624000 20.537000
48
6.483000 27.595000
4.041000 3.602000
24.350000 10.291000
30.836000 9.374000
11.020000 4.596000
24.021000 27.348000
23.199000 19.668000
24.484000 8.281000
4.734000 0.053000
1.999000 26.418000
27.938000 6.900000
3.788000 18.127000
0.467000 3.728000
14.893000 24.648000
22.483000 17.807000
2.421000 14.310000
6.617000 22.813000
9.514000 14.309000
7.616000 18.935000
17.451000 20.600000
5.249000 16.519000
31.556000 22.798000
30.303000 6.224000
11.008000 5.844000
32.609000 14.989000
32.702000 3.195000
20.485000 3.093000
14.343000 30.523000
1.587000 29.314000
9.503000 7.448000
25.200000 13.458000
6.618000 20.580000
19.796000 14.798000
15.281000 19.589000
20.798000 28.009000
27.157000 20.472000
23.622000 18.538000
12.292000 6.038000
24.179000 18.190000
29.657000 7.958000
6.191000 19.815000
22.888000 19.156000
11.511000 16.202000
2.634000 24.272000
20.055000 20.328000
22.646000 26.362000
4.886000 18.875000
28.433000 29.869000
42
23.844000 1.416000
21.881000 31.998000
10.322000 18.651000
10.021000 5.699000
3.557000 28.476000
27.892000 24.389000
5.075000 10.712000
2.600000 2.510000
21.003000 26.869000
17.861000 14.688000
13.401000 9.789000
15.255000 16.423000
5.002000 10.585000
24.182000 10.285000
27.088000 31.426000
28.617000 23.757000
9.832000 30.932000
4.169000 2.154000
25.721000 17.189000
19.976000 31.329000
2.368000 28.692000
21.425000 10.555000
3.434000 16.549000
7.441000 9.512000
30.145000 18.060000
21.718000 3.753000
16.139000 12.423000
16.279000 25.996000
16.687000 12.529000
22.549000 17.437000
19.866000 12.949000
0.193000 23.195000
3.297000 20.416000
28.286000 16.105000
24.488000 16.282000
12.455000 25.734000
18.114000 11.701000
31.316000 20.671000
5.786000 12.263000
4.313000 24.355000
31.185000 20.053000
0.912000 10.808000
32
20.945000 4.313000
27.756000 28.321000
19.558000 23.646000
27.982000 0.481000
4.144000 23.196000
20.222000 7.129000
2.161000 5.535000
20.450000 11.173000
10.466000 12.044000
21.659000 26.292000
26.439000 17.253000
20.024000 26.154000
29.510000 4.745000
20.649000 13.186000
8.313000 4.474000
28.022000 2.168000
14.018000 18.787000
9.905000 17.958000
7.391000 10.202000
3.625000 26.477000
4.414000 9.314000
25.824000 29.334000
25.874000 24.372000
20.159000 11.833000
28.070000 7.487000
28.297000 7.518000
8.177000 17.773000
32.270000 1.763000
2.668000 17.192000
13.985000 3.102000
8.480000 29.213000
7.627000 4.802000
49
30.527000 2.625000
1.543000 1.924000
11.023000 29.972000
13.061000 14.181000
31.003000 27.432000
17.505000 27.593000
22.725000 13.031000
8.492000 0.142000
17.222000 31.286000
13.064000 7.900000
19.187000 8.360000
22.413000 30.974000
14.270000 29.170000
0.235000 30.833000
19.711000 25.760000
18.896000 4.667000
7.285000 12.550000
0.140000 13.694000
2.695000 21.624000
28.019000 2.125000
26.576000 21.694000
22.658000 26.302000
17.371000 22.466000
4.678000 22.593000
23.851000 25.484000
1.018000 28.464000
21.119000 23.152000
2.800000 18.087000
31.060000 1.926000
9.010000 4.757000
32.170000 20.315000
9.576000 30.227000
12.043000 22.758000
7.164000 5.109000
7.882000 17.086000
29.565000 3.487000
29.577000 14.474000
2.625000 25.627000
5.629000 31.928000
25.423000 28.520000
6.902000 14.962000
0.123000 24.596000
3.737000 13.261000
10.195000 32.525000
1.264000 8.260000
6.202000 8.116000
5.030000 20.326000
29.011000 30.771000
6.411000 25.547000
3
21.520000 29.790000
14.924000 30.188000
21.763000 4.940000
1
18.662000 13.829000
13
18.958000 17.578000
8.365000 13.007000
11.477000 1.200000
26.058000 6.439000
2.303000 12.760000
19.357000 2.324000
6.477000 5.108000
21.113000 14.887000
19.801000 22.850000
14.460000 22.428000
12.993000 27.384000
19.405000 6.540000
31.111000 28.704000
35
32.356000 6.072000
29.350000 18.823000
14.485000 20.556000
23.216000 1.626000
9.357000 8.526000
13.357000 29.337000
23.271000 23.869000
29.361000 12.896000
13.022000 29.617000
10.112000 12.717000
18.696000 11.585000
24.041000 24.423000
24.129000 24.229000
4.565000 6.559000
8.932000 22.296000
29.855000 12.053000
16.962000 3.584000
29.734000 6.654000
16.972000 21.457000
14.369000 22.532000
2.963000 2.607000
2.483000 0.911000
11.635000 10.067000
22.848000 4.675000
12.938000 2.223000
22.142000 23.754000
6.511000 22.741000
20.175000 21.459000
17.825000 3.221000
17.870000 1.626000
31.934000 15.205000
31.783000 23.850000
17.398000 22.279000
22.701000 12.193000
12.734000 1.637000
34
5.556000 1.993000
10.176000 25.705000
6.962000 10.548000
15.881000 0.300000
14.413000 16.641000
19.855000 24.855000
13.142000 11.462000
27.611000 30.877000
20.424000 32.678000
1.752000 18.443000
28.296000 12.673000
10.040000 9.313000
0.875000 20.072000
12.818000 0.610000
1.017000 14.932000
28.112000 30.695000
13.169000 23.831000
20.040000 26.488000
28.685000 19.090000
19.497000 2.589000
25.990000 15.145000
19.353000 19.314000
18.651000 26.740000
22.044000 11.258000
0.335000 8.759000
11.192000 7.605000
25.264000 12.181000
28.503000 3.829000
23.775000 20.608000
29.292000 5.997000
17.549000 29.556000
25.561000 31.627000
6.467000 29.541000
26.129000 31.240000
13
29.174000 20.601000
6.077000 20.215000
8.683000 8.213000
23.992000 25.824000
5.601000 23.392000
15.759000 2.670000
26.428000 28.027000
4.084000 10.075000
18.786000 15.498000
24.970000 6.287000
23.847000 32.604000
0.503000 21.221000
22.663000 5.706000
13
9.010000 22.171000
27.489000 18.240000
12.164000 25.542000
7.619000 20.913000
7.591000 6.704000
31.818000 9.232000
0.750000 25.205000
4.975000 1.539000
0.303000 11.422000
21.098000 11.247000
13.584000 13.648000
2.971000 17.864000
22.913000 11.075000
45
28.712000 17.546000
18.678000 1.769000
15.262000 8.519000
13.985000 28.289000
15.944000 2.865000
18.540000 23.245000
25.508000 28.318000
27.870000 9.601000
28.323000 21.132000
24.472000 27.152000
25.087000 28.570000
29.763000 29.901000
17.103000 14.423000
3.527000 11.600000
26.969000 14.015000
5.565000 0.028000
21.543000 25.347000
2.088000 2.943000
12.637000 22.409000
26.463000 5.049000
4.681000 1.588000
11.342000 0.608000
32.060000 21.221000
1.758000 29.954000
20.888000 14.146000
0.690000 7.949000
12.843000 21.430000
25.620000 0.748000
27.067000 4.536000
20.783000 18.035000
32.226000 15.185000
7.038000 9.853000
25.629000 11.224000
15.748000 19.923000
3.359000 32.257000
24.766000 4.944000
14.955000 23.318000
32.726000 25.411000
21.025000 20.355000
31.001000 22.549000
9.496000 18.584000
9.515000 17.964000
23.342000 8.075000
17.913000 16.142000
31.196000 21.948000
22
20.426000 14.606000
26.173000 24.429000
32.404000 6.705000
20.626000 29.812000
19.375000 30.093000
16.565000 16.036000
14.736000 29.141000
30.814000 5.994000
8.256000 6.652000
23.936000 30.838000
20.482000 1.355000
21.015000 1.131000
18.230000 17.841000
14.625000 2.011000
32.637000 4.186000
19.690000 1.650000
5.662000 21.634000
10.893000 10.353000
21.416000 13.452000
14.008000 7.262000
22.233000 5.454000
16.303000 16.634000
3
14.256000 0.148000
11.124000 12.317000
4.213000 27.109000
28
29.200000 21.080000
21.318000 16.858000
24.050000 24.155000
31.361000 15.264000
11.903000 3.676000
29.643000 26.909000
14.902000 3.561000
28.489000 24.948000
1.282000 13.653000
30.674000 2.220000
5.402000 6.923000
3.831000 19.369000
3.878000 20.259000
19.008000 22.619000
23.971000 30.003000
21.945000 9.781000
26.504000 12.392000
32.685000 25.313000
6.698000 5.589000
12.722000 5.938000
19.037000 6.410000
31.461000 6.234000
12.508000 9.961000
3.959000 6.493000
1.515000 25.269000
24.937000 28.869000
0.058000 14.700000
13.971000 26.264000
0

OUTPUT:

Code: Select all

Region #1:
(0.2,0.3)-(0.8,12.3)-(3.0,22.2)-(5.4,32.4)-(27.6,32.7)-(31.1,24.4)-(32.8,20.0)-(30.1,9.0)-(24.5,5.7)-(11.5,1.9)-(1.8,0.3)-(0.2,0.3)
Perimeter length = 111.34

Region #2:
(13.9,26.3)-(16.9,32.4)-(18.8,11.8)-(5.0,7.4)-(13.9,26.3)
Perimeter length = 62.95

Region #3:
(11.3,5.5)-(1.1,16.9)-(2.3,31.7)-(28.7,26.9)-(29.7,22.7)-(30.2,18.0)-(31.1,4.6)-(15.6,4.0)-(11.3,5.5)
Perimeter length = 99.43

Region #4:
(0.9,32.6)-(16.4,29.2)-(27.6,20.5)-(32.2,9.8)-(18.8,1.7)-(0.9,32.6)
Perimeter length = 93.17

Region #5:
(0.5,3.7)-(1.6,29.3)-(14.3,30.5)-(28.4,29.9)-(31.6,22.8)-(32.6,15.0)-(32.7,3.2)-(4.7,0.1)-(0.5,3.7)
Perimeter length = 113.71

Region #6:
(4.2,2.2)-(2.6,2.5)-(0.9,10.8)-(0.2,23.2)-(2.4,28.7)-(9.8,30.9)-(21.9,32.0)-(27.1,31.4)-(31.3,20.7)-(31.2,20.1)-(23.8,1.4)-(4.2,2.2)
Perimeter length = 105.43

Region #7:
(14.0,3.1)-(2.2,5.5)-(2.7,17.2)-(3.6,26.5)-(8.5,29.2)-(25.8,29.3)-(27.8,28.3)-(32.3,1.8)-(28.0,0.5)-(14.0,3.1)
Perimeter length = 103.83

Region #8:
(1.5,1.9)-(0.1,13.7)-(0.1,24.6)-(0.2,30.8)-(5.6,31.9)-(10.2,32.5)-(29.0,30.8)-(31.0,27.4)-(32.2,20.3)-(31.1,1.9)-(8.5,0.1)-(1.5,1.9)
Perimeter length = 117.33

Region #9:
(21.5,29.8)-(14.9,30.2)-(21.8,4.9)-(21.5,29.8)
Perimeter length = 57.62

Region #10:
(18.7,13.8)-(18.7,13.8)
Perimeter length = 0.00

Region #11:
(6.5,5.1)-(2.3,12.8)-(13.0,27.4)-(31.1,28.7)-(26.1,6.4)-(19.4,2.3)-(11.5,1.2)-(6.5,5.1)
Perimeter length = 90.00

Region #12:
(6.5,22.7)-(13.0,29.6)-(31.8,23.9)-(32.4,6.1)-(23.2,1.6)-(2.5,0.9)-(6.5,22.7)
Perimeter length = 99.99

Region #13:
(12.8,0.6)-(5.6,2.0)-(0.3,8.8)-(0.9,20.1)-(6.5,29.5)-(20.4,32.7)-(25.6,31.6)-(28.1,30.7)-(28.7,19.1)-(29.3,6.0)-(28.5,3.8)-(15.9,0.3)-(12.8,0.6)
Perimeter length = 103.74

Region #14:
(4.1,10.1)-(0.5,21.2)-(23.8,32.6)-(26.4,28.0)-(29.2,20.6)-(25.0,6.3)-(15.8,2.7)-(4.1,10.1)
Perimeter length = 89.49

Region #15:
(0.3,11.4)-(0.8,25.2)-(12.2,25.5)-(27.5,18.2)-(31.8,9.2)-(5.0,1.5)-(0.3,11.4)
Perimeter length = 91.03

Region #16:
(2.1,2.9)-(0.7,7.9)-(1.8,30.0)-(3.4,32.3)-(29.8,29.9)-(32.7,25.4)-(32.2,15.2)-(25.6,0.7)-(5.6,0.0)-(2.1,2.9)
Perimeter length = 112.64

Region #17:
(14.6,2.0)-(8.3,6.7)-(5.7,21.6)-(14.7,29.1)-(19.4,30.1)-(23.9,30.8)-(32.4,6.7)-(32.6,4.2)-(21.0,1.1)-(14.6,2.0)
Perimeter length = 90.79

Region #18:
(14.3,0.1)-(11.1,12.3)-(4.2,27.1)-(14.3,0.1)
Perimeter length = 57.66

Region #19:
(11.9,3.7)-(4.0,6.5)-(0.1,14.7)-(1.5,25.3)-(24.0,30.0)-(32.7,25.3)-(31.5,6.2)-(30.7,2.2)-(11.9,3.7)
Perimeter length = 103.07

Gourav.in · Post by **Gourav.in** » Sat May 28, 2011 10:45 pm

shouldnt the output of this input

Code: Select all

output

Code: Select all

Region #1:
(0.0,0.5)-(0.0,1.0)-(0.5,1.0)-(1.0,1.0)-(1.0,0.5)-(1.0,0.0)-(0.5,0.0)-(0.0,0.0)-(0.0,0.5)
Perimeter length = 4.00

plzz help ??

Gourav.in · Post by **Gourav.in** » Mon May 30, 2011 3:12 am

Got it accpeted

the ouput should be

Code: Select all

Region #1:
(0.0,0.5)-(0.0,1.0)-(0.5,1.0)-(1.0,1.0)-(1.0,0.5)-(1.0,0.0)-(0.5,0.0)-(0.0,0.0)-(0.0,0.5)
Perimeter length = 4.00

bananeeek · Post by **bananeeek** » Sat Jun 08, 2013 6:55 am

Hi there, I`ve been struggling for some hours to get my project through this uva judge, but I`m still getting WA although I`ve checked everything like ten times. I`ve also tried all the possible inputs I`ve found on this forum so far and I`m getting the correct answers all the time... Got no idea what might be wrong with the code... I`ve made sure that the collinear points are computed correctly... Also I`m wrapping the points counterclockwise so while outputting the answer I`m using reverse iterator. Here`s the code:

Code: Select all

#include <cstdio>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std;

unsigned n;
float minx, miny;
float ax = 1.0;
float ay = 0.0;
float la = 1.0;
// for vector parallel to x-axis

struct  point
{
	float alfa;
	float x;
	float y;	
};

float ccw(point p1, point p2, point p3)
{
	return ( (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) );
}	// checking if every three points are turning clockwise or ccw



float angle(float x, float y)
{
	float len = sqrt( (x - minx)*(x - minx) + (y - miny)*(y - miny) );
	float kx = x - minx;
	float ky = y - miny;
	
	float c = ((ax)*(kx) + (ay)*(ky))/(la*len);
			float alfa = acos(c)*180/3.141592;
						if(alfa != alfa) alfa = -1.0;
			alfa = ceilf(alfa * 100) / 100;				
						
	return alfa;
} // computing angles 


struct pkt_less {
    bool operator ()(point const& a, point const& b) const {
        if (a.alfa < b.alfa) return true;
        if (a.alfa > b.alfa) return false;

        return false;
    }
}; // to sort the vector by alfa angle


struct soz {
    bool operator ()(point const& a, point const& b) const {
        if ((sqrt( ((a).x - minx)*((a).x - minx) + 
		((a).y - miny)*((a).y - miny) ) -
		 sqrt( (((b)).x - minx)*(((b)).x - minx) + 
		(((b)).y - miny)*(((b)).y - miny) ) ) <= 0 ) {return false; }
        else return true;
    }
}; // to sort the swapper vector by distance from the lowest y.coord and x.coord vertex

	
int main()
{	
	unsigned c = 0;
	float x, y;

	vector<point> points;
	vector<point>::iterator p;

	
	while( (scanf("%d",&n)) != 0 && n!=0)
	{ ++c;
		minx = miny = 1000000.0;
		
		for(unsigned i=0;i<n;++i)
			points.push_back(point());

		
		for(p=points.begin();p!=points.end();++p)
		{
			scanf("%f %f",&x,&y);
			(*p).x = x; (*p).y = y;
			if(y<miny) { miny=y; minx = x;}
			else if(y==miny) { if(x<minx) {minx = x;} }
		}

	for(p=points.begin();p!=points.end();++p)
		(*p).alfa = angle((*p).x, (*p).y);				
			

	sort(points.begin(), points.end(), pkt_less());	//sorting points vector so the vertices are in increasing polar angle with x-axis
		
	for(p = points.begin(); p!=(points.end()) ;++p) // taking care of collinear vertices so they are computed in the right order
	{unsigned r=0;
	vector<point> swapper;
	swapper.push_back(*p);
		while( ((*p).alfa) == ((*(p+1)).alfa) && p!=points.end()-1 )
		{
			swapper.push_back(*(p+1));
		++p;
		++r;
		}
		if(swapper.size()>1)
		{	
			sort(swapper.begin(), swapper.end(), soz() );
			points.erase(p-r,p+1);
			points.insert(p-r, swapper.begin(), swapper.end());
		}
	swapper.clear();
	}

	vector<point> hull;
	vector<point>::iterator it,j;
	
	if(n>1)
	{
	hull.push_back(*(points.begin()));
	hull.push_back(*(points.begin()+1));
	
	
	for(p=points.begin()+2;p!=points.end();++p)
	{it = j = hull.end()-1; --it; 
	
		if(ccw((*it),(*j),(*p)) >= 0){ hull.push_back(*p);} // checking every 3 points, 2 top from hull stack and one from the rest available
		else
		{it = j = hull.end()-1; --it;
		 while( (ccw((*it),(*j),(*p)) <= 0 )) { hull.pop_back(); it = j = hull.end()-1; --it;}
		 hull.push_back(*p);
		}
	}
	hull.push_back(*(points.begin()));

	}else
	hull.push_back(*(points.begin()));
	
	
	float distance = 0.0;

	printf("Region #%d:\n",c);
		for(vector<point>::reverse_iterator rit=hull.rbegin(); rit!=hull.rend();++rit)
		{
			if(rit!=hull.rbegin()) printf("-");
			printf("(%.1f,%.1f)",(*rit).x, (*rit).y);
if(rit!=hull.rend()-1) distance  += ( sqrt( ((*(rit+1)).x - (*rit).x) * ((*(rit+1)).x - (*rit).x) + ((*(rit+1)).y - (*rit).y) * ((*(rit+1)).y - (*rit).y)  ) );

	
		}
		printf("\nPerimeter length = %.2f\n\n", distance);
		

	points.clear();
	hull.clear();		
}

return 0;
}

bananeeek · Post by **bananeeek** » Sat Jun 08, 2013 4:54 pm

okay, I know what's wrong.. It was alrdy 4a.m when I was dealing with those collinear points, and I screwed pretty much... there are 2 issues I noticed so far, first if there`s only one line of points in total, and they`re collinear, then the convex hull must contain all of the inner vertices twice, it grabs each one on the way out, and each when it gets back... But if there are some more points except starting point and collinear points, there`s no need to add those vertices twice... The second issue is trickier and I'm still trying to figure out on what conditions it should work... My graham algorithm goes counterclockwise so the collinear vertices with the lowest polar angle have to be sorted in increasing by distance to the min_x min_y order, and now that I`m thinking about it, all the collinear points except those with highest polar angle should be sorted that way... By collinear points I`m dealing with here I mean points with the same polar angle... If anyone spots something wrong please let me know.. I`ll post the code after modifications coz i have a feeling that there will still be something wrong...

bananeeek · Post by **bananeeek** » Sat Jun 08, 2013 5:34 pm

okay, now I`m pretty sure I`ve covered it all. I ran like 20 tests on collinear points covering every possible situations with collinear points, but still getting WA from the judge... here`s the modified code, and I`m pretty clueless right now...

Code: Select all

#include <cstdio>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

unsigned n;
float minx, miny;
float ax = 1.0;
float ay = 0.0;
float la = 1.0;


struct  point
{
	float alfa;
	float x;
	float y;	
};




float ccw(point p1, point p2, point p3)
{
	return ( (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) );
}		



float angle(float x, float y)
{
	float len = sqrt( (x - minx)*(x - minx) + (y - miny)*(y - miny) );
	float kx = x - minx;
	float ky = y - miny;
	
	float c = ((ax)*(kx) + (ay)*(ky))/(la*len);
			float alfa = acos(c)*180/3.141592;
						if(alfa != alfa) alfa = -1.0;
			alfa = ceilf(alfa * 100) / 100;				
						
	return alfa;
}


struct pkt_less {
    bool operator ()(point const& a, point const& b) const {
        if (a.alfa < b.alfa) return true;
        if (a.alfa > b.alfa) return false;

        return false;
    }
};


struct soz {
    bool operator ()(point const& a, point const& b) const {
        if ((sqrt( ((a).x - minx)*((a).x - minx) + 
		((a).y - miny)*((a).y - miny) ) -
		 sqrt( (((b)).x - minx)*(((b)).x - minx) + 
		(((b)).y - miny)*(((b)).y - miny) ) ) <= 0 ) {return false; }
        else return true;
    }
}; //sorting in decreasing order


struct sozfirst {
    bool operator ()(point const& a, point const& b) const {
        if ((sqrt( ((a).x - minx)*((a).x - minx) + 
		((a).y - miny)*((a).y - miny) ) -
		 sqrt( (((b)).x - minx)*(((b)).x - minx) + 
		(((b)).y - miny)*(((b)).y - miny) ) ) <= 0 ) {return true; }
        else return false;
    }
}; //sorting in increasing order


	
int main()
{	
	bool coll,ool;
	unsigned c = 0;
	float x, y;

	vector<point> points;
	vector<point>::iterator p;

	
	while( (scanf("%d",&n)) != 0 && n!=0)
	{ ++c;
		minx = miny = 1000000.0;
		coll = true;
		ool = false;
		
		for(unsigned i=0;i<n;++i)
			points.push_back(point());

		
		for(p=points.begin();p!=points.end();++p)
		{
			scanf("%f %f",&x,&y);
			(*p).x = x; (*p).y = y;
			if(y<miny) { miny=y; minx = x;}
			else if(y==miny) { if(x<minx) {minx = x;} }
		}

	for(p=points.begin();p!=points.end();++p)
		(*p).alfa = angle((*p).x, (*p).y);				
			

	sort(points.begin(), points.end(), pkt_less());	
	
		
	for(p = points.begin(); p!=(points.end()) ;++p)
	{unsigned r=0;
	vector<point> swapper;
	swapper.push_back(*p);
		while( ((*p).alfa) == ((*(p+1)).alfa) && p!=points.end()-1 )
		{
			swapper.push_back(*(p+1));
		++p;
		++r;
		}
		if(swapper.size()>1)
		{ if(p==points.end()-1) { coll = false; } // the last line of points which are all collinear, also with hughest polar angle
		                                                        
			if(coll )sort(swapper.begin(), swapper.end(), sozfirst() );
			else sort(swapper.begin(), swapper.end(), soz() ); //sorting in increasing order all the collinear lines of points except the last line  
			                                                                           //of collinear points, which is sorted in decreasing order (true case in this if)
			if((swapper.size()) == (points.size()-1)){ ool = true; }
			

			points.erase(p-r,p+1);
			points.insert(p-r, swapper.begin(), swapper.end());
			
			if(ool) //ool stands for only one line
			{
				for(vector<point>::iterator s = swapper.begin()+1;s!=swapper.end();++s)
					points.insert(p-r,*s);
				break;
			} // making sure that if there's ool, inner points will be computed twice
			

		}
	swapper.clear();
	}
			

	vector<point> hull;
	vector<point>::iterator it,j;
	
	if(n>1)
	{
	hull.push_back(*(points.begin()));
	hull.push_back(*(points.begin()+1));
	
	
	for(p=points.begin()+2;p!=points.end();++p)
	{it = j = hull.end()-1; --it; 
	
		if(ccw((*it),(*j),(*p)) >= 0){ hull.push_back(*p);}
		else
		{it = j = hull.end()-1; --it;
		 while( (ccw((*it),(*j),(*p)) <= 0 )) { hull.pop_back(); it = j = hull.end()-1; --it;}
		 hull.push_back(*p);
		}
	}
	hull.push_back(*(points.begin()));

	}else
	hull.push_back(*(points.begin()));
	
	
	float distance = 0.0;

	printf("Region #%d:\n",c);
		for(vector<point>::reverse_iterator rit=hull.rbegin(); rit!=hull.rend();++rit)
		{
			if(rit!=hull.rbegin()) printf("-");
			printf("(%.1f,%.1f)",(*rit).x, (*rit).y);
if(rit!=hull.rend()-1) distance  += ( sqrt( ((*(rit+1)).x - (*rit).x) * ((*(rit+1)).x - (*rit).x) + ((*(rit+1)).y - (*rit).y) * ((*(rit+1)).y - (*rit).y)  ) );

	
		}
		printf("\nPerimeter length = %.2f\n\n", distance);
		

	points.clear();
	hull.clear();		
}

return 0;
}

bananeeek · Post by **bananeeek** » Sat Jun 08, 2013 7:35 pm

upgrade for one point input, now the output consiists of route from the point to itself... still WA, someone posted some auto generatoed points with correct output, and I got it all right with my code
http://online-judge.uva.es/board/viewto ... =218#p5388
still WA

brianfry713 · Post by **brianfry713** » Wed Jun 12, 2013 2:04 am

Try using double instead of float.

bananeeek · Post by **bananeeek** » Thu Jun 13, 2013 3:33 am

I changed every float to double and widen the alfa angle precision, still WA...
I also tried another implementation of graham scan, it sorts the vertices by coordinates, not by polar angle range, and it computes 2 loops, first the upper convex hull, then the bottom part. The code goes like this:

Code: Select all

#include <cstdio>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std;

unsigned n;


struct  point
{
	double x;
	double y;	
};


double ccw(point p1, point p2, point p3)
{
	return ( (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) );
}		

bool porownaj(point a, point b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}


int main()
{	

	unsigned c = 0;
	double x, y;

	vector<point> points;
	vector<point>::iterator p;

	
	while( (scanf("%d",&n)) != 0 && n!=0)
	{ ++c;
	if(c>1) printf("\n");


		
		for(unsigned i=0;i<n;++i)
			points.push_back(point());

		
		for(p=points.begin();p!=points.end();++p)
		{
			scanf("%lf %lf",&x,&y);
			(*p).x = x; (*p).y = y;
		}		

	sort(points.begin(), points.end(),porownaj);	


	

			

	vector<point> hull;
	vector<point>::iterator it,j;
	
	if(n>1)
	{
	hull.push_back(*(points.begin()));
	hull.push_back(*(points.begin()+1));
	
	
	for(p=points.begin()+2;p!=points.end();++p)
	{it = j = hull.end()-1; --it; 
	
		if(ccw((*it),(*j),(*p)) <= 0){ hull.push_back(*p);}
		else
		{it = j = hull.end()-1; --it;
		 while( (ccw((*it),(*j),(*p)) > 0 )) { hull.pop_back(); it = j = hull.end()-1; --it;}
		 hull.push_back(*p);
		}
	}
	for(vector<point>::reverse_iterator rit = points.rbegin()+1; rit!=points.rend();++rit)
	{it = j = hull.end()-1; --it; 
	
		if(ccw((*it),(*j),(*rit)) <= 0){ hull.push_back(*rit);}
		else
		{it = j = hull.end()-1; --it;
		 while( (ccw((*it),(*j),(*rit)) > 0 )) { hull.pop_back(); it = j = hull.end()-1; --it;}
		 hull.push_back(*rit);
		}
		
	}
	}else
	{
	hull.push_back(*(points.begin()));
	hull.push_back(*(points.begin()));

	}

	double distance = 0.0;

	printf("\nRegion #%d:\n",c);
		for(p=hull.begin(); p!=hull.end();++p)
		{
			if(p!=hull.begin()) printf("-");
			printf("(%.1f,%.1f)",(*p).x, (*p).y);
if(p!=hull.end()-1) distance  += ( sqrt( ((*(p+1)).x - (*p).x) * ((*(p+1)).x - (*p).x) + ((*(p+1)).y - (*p).y) * ((*(p+1)).y - (*p).y)  ) );
	
		}
		printf("\nPerimeter length = %.2f", distance);
		

	points.clear();
	hull.clear();		
}

return 0;
}

but it gives me runtime error, so I guess I must`ve messed up with a pointer somewhere, but havent found it yet....

brianfry713 · Post by **brianfry713** » Thu Jun 13, 2013 11:40 pm

Doesn't match the sample I/O.

sady · Post by **sady** » Sat Oct 11, 2014 9:31 am

plz help

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<stack>
#include<cmath>
#define limit 12000000
class Pair
{
    public:
        double x,y;
};
Pair ob[limit], pre;
int trap;
void lowest_y();
void sort_CCW_order();
double dis(Pair a, Pair b)
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int cross_product(Pair p0,Pair p1, Pair p2)
{

    return ( (p1.x-p0.x)*(p2.y-p0.y) )-( (p2.x-p0.x)*(p1.y-p0.y) );

}
int comp(const void *P1, const void *P2)
{
    Pair *p1= (Pair *)P1;
    Pair *p2=(Pair *)P2;
    int x=cross_product(ob[0], *p1 , *p2);
    //printf("%d::",x);
    if(x>0)
    {
        //printf("(%0.1lf, %0.1lf) , (%0.1lf, %0.1lf) , (%0.1lf, %0.1lf) are CounterCW order\n", ob[0].x, ob[0].y, p1->x,p1->y,p2->x,p2->y);
        return -1;
    }
    else if(x<0)
    {
        //printf("(%0.1lf, %0.1lf) , (%0.1lf, %0.1lf) , (%0.1lf, %0.1lf) are ClockWise order\n", ob[0].x, ob[0].y, p1->x,p1->y,p2->x,p2->y);
        return 1;
    }
    //printf("(%0.1lf, %0.1lf) , (%0.1lf, %0.1lf) , (%0.1lf, %0.1lf) are Collinear\n", ob[0].x, ob[0].y, p1->x,p1->y,p2->x,p2->y);
    return ( (dis(ob[0], *(Pair *)P1)<=dis(ob[0], *(Pair *)P2) )?-1:1 );
}
Pair next_to_top(std::stack<Pair> s);
void print(double &perimeter );
void Graham_scan();
int main()
{
    int r=0;
    while(scanf("%d", &trap)==1 && trap)
    {
        for(int i=0;i<trap;++i)
        {
            scanf("%lf %lf", &ob[i].x, &ob[i].y );
        }
        ++r;
        if(r>1)puts("");
        printf("Region #%d:\n", r);
        Graham_scan();
    }

    return 0;
}
void lowest_y()
{
    Pair pt;
    pt=ob[0];
    int ind=0;
    for(int i=1;i<trap;++i)
    {
        if(ob[i].y <pt.y  || (ob[i].y==pt.y && ob[i].x<pt.x) )
        {
            pt=ob[i];
            ind=i;
        }
    }
    ob[ind]=ob[0];
    ob[0]=pt;
}
void sort_CCW_order()
{
    qsort(&ob[1], trap-1, sizeof(Pair), comp);
}
Pair next_to_top(std::stack<Pair> s)
{
    Pair pt, temp;
    pt=s.top();
    s.pop();
    temp=s.top();
    s.push(pt);
    return temp;
}
void print(double &perimeter ,std::stack<Pair> s)
{
    if(s.empty()) return;
    Pair cur=s.top();
    s.pop();
    perimeter+= sqrt( dis(pre,cur) );
    pre=cur;
    printf("-(%0.1lf,%0.1lf)", cur.x, cur.y);
    print(perimeter, s);

}
void Graham_scan()
{
    lowest_y();

    sort_CCW_order();
    /*for(int i=0;i<trap;++i)
    {
        printf("%0.1lf %0.1lf\n",ob[i].x, ob[i].y);
    }
    //puts("hi");*/
    std::stack<Pair> s;
    s.push(ob[0]);
    s.push(ob[1]);
    s.push(ob[2]);
    for(int i=3;i<trap;++i)
    {
        while( cross_product(next_to_top(s), s.top(), ob[i])<=0  )
        {
            //printf("popping %0.1lf %0.1lf\n",s.top().x, s.top().y );
            s.pop();
        }

        s.push(ob[i]);
    }
    //puts("hi");
    pre=ob[0];
    double p=0;
    printf("(%0.1lf,%0.1lf)", ob[0].x,ob[0].y);
    print(p,s);
    puts("");
    printf("Perimeter length = %0.2lf\n", p);
    return;

}

OJ Board

218 - Moth Eradication

Pls help us

Re: 218 - WA

Re: 218 - WA

218 - Moth Eradiction WA

Re: 218 - Moth Eradiction WA

Re: 218 - Moth Eradiction WA

Re: 218 - Moth Eradiction WA

Re: 218 - Moth Eradiction WA

Re: 218 - Moth Eradiction WA

Re: 218 - Moth Eradiction WA

Re: 218 - Moth Eradication runtime error