10065 - Useless Tile Packers

[Shuvra(CSE-BUET)]

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

[Martin Macko]

There is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=8876 and http://online-judge.uva.es/board/viewtopic.php?t=2661)

All about problems in Volume C. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

[Shuvra(CSE-BUET)]

Thanks Mr. Martin Macko. But is it the answer of my question? I read all the previous posts about it.

[Martin Macko]

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

Draw it on paper! You'll see that the wasted area in this example is: ([0,0], [2,1], [4,1]) and ([1,4], [4,4], [2,3]) and is equal to 2.5, what is 18.52% of the total area (13.5).

Btw, the practice not to create duplicate threads on problems is there for reason. It's an attempt to make the board less messy, so it's easier to search it for relevant information on problems you need some help with.

[Shuvra(CSE-BUET)]

I can't realise how to calculate wasted area , which interbal points I have to consider and how. Pls explain me.

[Martin Macko]

I can't realise how to calculate wasted area , which interbal points I have to consider and how. Pls explain me.

Just count the area of the convex hull and substract the area of the input polygon from it.

[icylord]

AC

[aansu]

can someone give me critical cases? I tried all cases on this thread, my pro is running perfectly for all of them. But still WA