## 10065 - Useless Tile Packers

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### 10065 - Useless Tile Packers

I try to solve this problem using Graham-scan, but got WA. Could anyone tell me some special inputs for this problem ?
Maybe anyone want to look at me code and try to find my mistake ? If anyone want - I send him/her my code )

I don't want to post source on board ....

Regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I also used Graham and got AC-ed ... I don't see any trick in this ... as long as we know how to compute Area and Convex Hull of polygon. Could it be floating-point problem ?

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I found mistake in Graham-scan.. it was silly, but still WA

I use this formula to compute area of polygon (vertex are sorted in way are placed on border of hull):

S = 0.5*SUM(i)[(x-x[i-1])*(y+y[i+1])] for i = 0..N

I think that formula is correct ....

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
The formula of area that you have can be negative, right ??? Could that be the problem ???

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
sure , it could be nagative but I use fabs() to change negative to positive

maybe you want to take a look at my code ?

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Today I got Accepted. I found a small mistake in code, which sort points ...
Thanks all for help

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

hj
New poster
Posts: 5
Joined: Sun May 25, 2003 11:56 am

### 10065 (WA)

HI!!
I keep getting WA with this problem. I cannot find mistake in my program. Could somebody
help or give me some test cases ?
[cpp]
#include <iostream>
#include <cmath>

#define MAX 102

using namespace std;

struct point {
double x,y;
} t[MAX];

double area(int i, int j, int n){
double ptmp;
ptmp=0.0;
for (int p=i;p<j;++p) ptmp+=(t[p%n].x*t[(p+1)%n].y-t[(p+1)%n].x*t[p%n].y);

ptmp+=t[j%n].x*t[i%n].y-t[i%n].x*t[j%n].y;
return ptmp*0.5;
}

int main(){

int n,tile=0;
cout.setf(ios::fixed);
cout.precision(2);
cin >> n;
while(n){
++tile;
for(int i=0;i<n;++i) cin >> t.x>> t.y;
double sp=area(0,n-1,n);
int sign=1;
if (sp<0) {sp=-sp; sign=-sign;}
int is=0;
double sw=0.0;
while(is<n){
int i1=is;
while (i1<n && area(i1,i1+2,n)*sign<0){
++i1;
}
if (is<i1) { sw+=fabs(area(is,i1+1,n)); is=i1+1; } else ++is;
}

cout<<"Tile #"<<tile<<endl;
cout<<"Wasted Space = "<< sw/(sp+sw)*100<<" %"<<endl;
cout<<endl;
cin >> n;
}
return 0;
}
[/cpp]
thanks for any help and HAPPY NEW YEAR !!

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### 10065

Hi all,
I need some i/o for this problem. I'm getting WA. Please someone provide me some i/o. Thanks in advance.
Some Love Stories Live Forever ....

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

### Re: I/O Needed For 10065 Useless Tile Packers

Hi, Raj Ariyan.
Following is the I/O which I prepared.
Try to debug by using this

Input :

Code: Select all

``````5
2 2
2 0
0 0
0 2
1 3
5
0 0
2 0
2 2
1 3
0 2
5
1 3
0 2
0 0
2 0
2 2
7
0 0
0 3
1 4
2 3
4 4
4 1
2 1
7
0 0
2 1
4 1
4 4
2 3
1 4
0 3
25
9 7
4 5
10 10
8 10
7 9
6 9
5 10
4 7
3 8
2 8
0 10
2 6
1 5
2 4
0 3
3 2
2 1
5 0
4 2
6 4
6 2
7 5
7 1
8 0
10 1
25
9 7
10 1
8 0
7 1
7 5
6 2
6 4
4 2
5 0
2 1
3 2
0 3
2 4
1 5
2 6
0 10
2 8
3 8
4 7
5 10
6 9
7 9
8 10
10 10
4 5
3
4 1
3 4
1 2
3
4 1
1 2
3 4
32
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
11 121
12 144
13 169
14 196
15 225
16 256
17 289
18 324
19 361
20 400
21 441
22 484
23 529
24 576
25 625
26 676
27 729
28 784
29 841
30 900
31 961
20
12 144
13 169
14 196
15 225
16 256
17 289
18 324
19 361
20 324
21 441
22 324
23 529
24 324
25 625
26 324
27 729
28 784
29 841
30 900
31 961
63
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81
10 100
11 121
12 144
13 169
14 196
15 225
16 256
17 289
18 324
19 361
20 400
21 441
22 484
23 529
24 576
25 625
26 676
27 729
28 784
29 841
30 900
31 961
32 900
33 841
34 784
35 729
36 676
37 625
38 576
39 529
40 484
41 441
42 400
43 361
44 324
45 289
46 256
47 225
48 196
49 169
50 144
51 121
52 100
53 81
54 64
55 49
56 36
57 25
58 16
59 9
60 4
61 1
62 0
0
``````
Output :
Tile #1
Wasted Space = 0.00 %

Tile #2
Wasted Space = 0.00 %

Tile #3
Wasted Space = 0.00 %

Tile #4
Wasted Space = 18.52 %

Tile #5
Wasted Space = 18.52 %

Tile #6
Wasted Space = 42.78 %

Tile #7
Wasted Space = 42.78 %

Tile #8
Wasted Space = 0.00 %

Tile #9
Wasted Space = 0.00 %

Tile #10
Wasted Space = 0.00 %

Tile #11
Wasted Space = 50.61 %

Tile #12
Wasted Space = 33.30 %
Best regards.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul
Hi Tan_yui,
Thanks for ur help. I found my mistake and got accepted . Thanks again.
Some Love Stories Live Forever ....

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

### A really strange CE at OJ.

Could anybody, please, explain what does the following CE mean?

Code: Select all

``````04823365_24.c:136746872: sorry, not implemented: use of `method_call_expr' in template
04823365_24.c:136746872: sorry, not implemented: use of `exact_div_expr' in template
04823365_24.c: In function `class vector<int,allocator<int> > convex_hull<int>(const vector<pair<int,int>,allocator<pair<int,int> > > &)':
04823365_24.c:55:   instantiated from here
04823365_24.c:136746872: invalid catch parameter
04823365_24.c:136746872: confused by earlier errors, bailing out
``````
I've been succesfully using templates for a log time and I've never had any compile problems with them here at OJ. However, today I've no idea what to do to have it compiled. (I want to keep using templated algorithms, so they work on any (suitable) data type with no need to rewrite it.)

Here is my code (to problem 10065) that have got this CE at OJ:
10065.cc wrote:Code removed after resolving the problem. Thanks.
Last edited by Martin Macko on Sun Aug 13, 2006 4:47 pm, edited 2 times in total.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Internal compiler error, nothing to see here folks, move along.

Seriously, change typedef pair<int,int> PII to a define or don't use it at all in definition of P if you want to avoid this problem with g++ 2.95.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Krzysztof Duleba wrote:Internal compiler error, nothing to see here folks, move along.

Seriously, change typedef pair<int,int> PII to a define or don't use it at all in definition of P if you want to avoid this problem with g++ 2.95.
Changing all typedefed PII to pair<int,int> didn't help. It gets the same compile errors. (I've edited my previous post so there is the modified (though bad) code.)

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
This is a very cool code, removing pretty much everything completely changes how the compiler behaves, so when I initially refactored it to make it more readable I accidentally made it work

g++ 2.95 is not perfect, nor is it's implemention of templates and __typeof, especially on literals. It seems that the best long-term solution for you to avoid ICEs it either to change the implementation of REP or to always make sure that in templates you call __typeof on variables, not on literals.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Krzysztof Duleba wrote:This is a very cool code, removing pretty much everything completely changes how the compiler behaves, so when I initially refactored it to make it more readable I accidentally made it work

g++ 2.95 is not perfect, nor is it's implemention of templates and __typeof, especially on literals. It seems that the best long-term solution for you to avoid ICEs it either to change the implementation of REP or to always make sure that in templates you call __typeof on variables, not on literals.
Thanks for your help. Yes, __typeof(2) caused the CE. Fortunately __typeof(int(2)) works, so I've changed REP(i,2) to REP(i,int(2)) in my code to get compiled at OJ.