10065 - Useless Tile Packers

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

Moderator: Board moderators

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

10065(USELESS TILE PACKERS) stuck in this prob

Post by Shuvra(CSE-BUET) » 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])
Life is a challenge.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

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

Post by Martin Macko » Thu Aug 31, 2006 11:14 am

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.

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

hey

Post by Shuvra(CSE-BUET) » Thu Aug 31, 2006 12:11 pm

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

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

Post by Martin Macko » Fri Sep 01, 2006 11:49 am

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.

Shuvra(CSE-BUET)
New poster
Posts: 19
Joined: Wed Jan 11, 2006 9:57 am
Location: Dhaka

I am really stuck

Post by Shuvra(CSE-BUET) » Fri Sep 01, 2006 5:06 pm

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: I am really stuck

Post by Martin Macko » Sat Sep 02, 2006 9:37 pm

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.

icylord
New poster
Posts: 1
Joined: Mon Dec 11, 2006 5:07 pm

10065 need help

Post by icylord » Sat Mar 10, 2007 10:57 am

AC

aansu
New poster
Posts: 3
Joined: Wed Oct 13, 2010 1:42 pm

Re: 10065 - Useless Tile Packers

Post by aansu » Wed Oct 13, 2010 1:46 pm

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 :(

Post Reply

Return to “Volume 100 (10000-10099)”