10065(USELESS TILE PACKERS) stuck in this prob
Posted: Thu Aug 31, 2006 7:01 am
I used graham scan to solve the prob and code is correct as I got acc in other probs. But what makes me crazy is that calculation of wasted area.
While graham scanning ,wasted area =sum of (negetive area),i.e clockwise turn.
I am posting the code segment of convex hull function now .
hh saves hull points ,pnt keeps sorted points(by increasing angle with the
lowermost and leftmost point)
hh[0][0] = pnt[0][0];
hh[0][1] = pnt[0][1];
index = 1;
prev = 0;
z=0.0;
while(1){
next = (prev+1) % n;
for( j=next,count=1 ; count<=n-2; count++ ){
i = (j+count) % n;
area = Area(prev,next,i);
if( area > 0.000001 ) continue;//!!! data sorted before
else if ( area < 0.000001 )
{
z+=.5 * fabs(Area(prev,next,i));//Area fn does not multiply by .5 and z is wasted area. area fn calculates area by 3 points
next = i;
}
else{
dis1 = Dis(prev,next);
dis2 = Dis(prev,i);
if( dis2 > dis1 ) next = i;
}
}
if( next==0) break;
else{
hh[index][0] = pnt[next][0];
hh[index][1] = pnt[next][1];
index++;
p=prev;
prev = next ;
}
}
return index;
}
.....
In the main I printed z/hull area
Another thing is that in a previous post there was a input
7
0 0 0 3 1 4 2 3 4 4 4 1 2 1
...............................
Output =18.52 %
But how it is possible? To my opinion wasted area is made by points( [4,1],[2,1],[4,4]) and ([4,4],[2,3],[1,4])
While graham scanning ,wasted area =sum of (negetive area),i.e clockwise turn.
I am posting the code segment of convex hull function now .
hh saves hull points ,pnt keeps sorted points(by increasing angle with the
lowermost and leftmost point)
hh[0][0] = pnt[0][0];
hh[0][1] = pnt[0][1];
index = 1;
prev = 0;
z=0.0;
while(1){
next = (prev+1) % n;
for( j=next,count=1 ; count<=n-2; count++ ){
i = (j+count) % n;
area = Area(prev,next,i);
if( area > 0.000001 ) continue;//!!! data sorted before
else if ( area < 0.000001 )
{
z+=.5 * fabs(Area(prev,next,i));//Area fn does not multiply by .5 and z is wasted area. area fn calculates area by 3 points
next = i;
}
else{
dis1 = Dis(prev,next);
dis2 = Dis(prev,i);
if( dis2 > dis1 ) next = i;
}
}
if( next==0) break;
else{
hh[index][0] = pnt[next][0];
hh[index][1] = pnt[next][1];
index++;
p=prev;
prev = next ;
}
}
return index;
}
.....
In the main I printed z/hull area
Another thing is that in a previous post there was a input
7
0 0 0 3 1 4 2 3 4 4 4 1 2 1
...............................
Output =18.52 %
But how it is possible? To my opinion wasted area is made by points( [4,1],[2,1],[4,4]) and ([4,4],[2,3],[1,4])