10065 - Useless Tile Packers

[Dominik Michniewski]

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

[turuthok]

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-

[Dominik Michniewski]

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

[turuthok]

The formula of area that you have can be negative, right ??? Could that be the problem ???

-turuthok-

[Dominik Michniewski]

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

[Dominik Michniewski]

Today I got Accepted. I found a small mistake in code, which sort points ...
Thanks all for help

DM

[hj]

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]

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

[tan_Yui]

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]

Hi Tan_yui,
Thanks for ur help. I found my mistake and got accepted . Thanks again.

[Martin Macko]

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:

Code removed after resolving the problem. Thanks.

[Krzysztof Duleba]

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.

[Martin Macko]

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]

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.

[Martin Macko]

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.