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])
10065 - Useless Tile Packers
Moderator: Board moderators
-
- New poster
- Posts: 19
- Joined: Wed Jan 11, 2006 9:57 am
- Location: Dhaka
10065(USELESS TILE PACKERS) stuck in this prob
Life is a challenge.
-
- 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.
-
- 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.
-
- 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
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).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])
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.
-
- 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.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: I am really stuck
Just count the area of the convex hull and substract the area of the input polygon from it.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.
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 
