### 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])