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

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.

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

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

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

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

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

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.

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

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

AC

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

### Re: 10065 - Useless Tile Packers

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