Page 1 of 2

### 10065 - Useless Tile Packers

Posted: Tue Apr 08, 2003 2:27 pm
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

Posted: Tue Apr 08, 2003 6:49 pm
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-

Posted: Wed Apr 09, 2003 7:59 am
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

Posted: Wed Apr 09, 2003 8:22 am
The formula of area that you have can be negative, right ??? Could that be the problem ???

-turuthok-

Posted: Wed Apr 09, 2003 9:11 am
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

Posted: Thu Apr 10, 2003 8:00 am
Today I got Accepted. I found a small mistake in code, which sort points ...
Thanks all for help

DM

### 10065 (WA)

Posted: Wed Dec 31, 2003 9:44 pm
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 !!

### 10065

Posted: Sat Sep 10, 2005 4:44 pm
Hi all,
I need some i/o for this problem. I'm getting WA. Please someone provide me some i/o. Thanks in advance.

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

Posted: Mon Sep 12, 2005 2:22 pm
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.

Posted: Mon Sep 12, 2005 4:10 pm
Hi Tan_yui,
Thanks for ur help. I found my mistake and got accepted . Thanks again.

### A really strange CE at OJ.

Posted: Sun Aug 13, 2006 12:55 am
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.

Posted: Sun Aug 13, 2006 1:25 am
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.

Posted: Sun Aug 13, 2006 1:37 am
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.)

Posted: Sun Aug 13, 2006 2:11 am
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.

Posted: Sun Aug 13, 2006 4:42 pm
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.