Page 2 of 2

10065(USELESS TILE PACKERS) stuck in this prob

Posted: Thu Aug 31, 2006 7:01 am
by 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])

Re: 10065(USELESS TILE PACKERS) stuck in this prob

Posted: Thu Aug 31, 2006 11:14 am
by 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)
forum 'Volume C' description wrote: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.

hey

Posted: Thu Aug 31, 2006 12:11 pm
by Shuvra(CSE-BUET)
Thanks Mr. Martin Macko. But is it the answer of my question? I read all the previous posts about it.

Re: 10065(USELESS TILE PACKERS) stuck in this prob

Posted: Fri Sep 01, 2006 11:49 am
by Martin Macko
Shuvra(CSE-BUET) wrote: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.

I am really stuck

Posted: Fri Sep 01, 2006 5:06 pm
by Shuvra(CSE-BUET)
I can't realise how to calculate wasted area , which interbal points I have to consider and how. Pls explain me.

Re: I am really stuck

Posted: Sat Sep 02, 2006 9:37 pm
by Martin Macko
Shuvra(CSE-BUET) wrote: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.

10065 need help

Posted: Sat Mar 10, 2007 10:57 am
by icylord
AC

Re: 10065 - Useless Tile Packers

Posted: Wed Oct 13, 2010 1:46 pm
by 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 :(