Page 4 of 4
Re: 10005 - Packing Polygons
Posted: Sat Jun 04, 2011 5:10 am
by hyperionsshrike
For additional information, this is my AC output:
Code: Select all
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
It seems that that sample input is a bit too sensitive to precision errors.
Re: 10005 - Packing Polygons
Posted: Mon Dec 24, 2012 11:32 pm
by brianfry713
Input:
Correct output:
Code: Select all
There is no way of packing that polygon.
The polygon can be packed in the circle.
Re: 10005 - Packing Polygons
Posted: Tue Dec 25, 2012 3:21 am
by brianfry713
Input:
Code: Select all
2
10 0
20 20
11.18
2
10 0
20 20
11.19
0
Correct output:
Code: Select all
There is no way of packing that polygon.
The polygon can be packed in the circle.
Re: 10005 - Packing Polygons
Posted: Tue Dec 25, 2012 8:38 pm
by brianfry713
Input from this thread:
Code: Select all
4
100 90
100 110
99 100
111 100
10.0
0
Correct output:
Code: Select all
There is no way of packing that polygon.
Re: 10005 - Packing Polygons
Posted: Sat Aug 02, 2014 4:58 pm
by lighted
Darko wrote:Well, otput of my AC program is:
There is no way of packing that polygon.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
I guess it means there are no cases with R=0 (I say you can't pack it, even if it is a single point). And for the 4th case, it changes with a change to EPS, I guess there are no corner cases like that.
LithiumDex wrote:I found this test data on the forum, however it was from years ago when the judges input would allow for many wrong solutions, could someone who has solved this problem recently please run this input and post the results?
Thanks
Code: Select all
1
2 2
0.0
2
5 1
-3 4
4.2720018
2
5 1
-3 4
4.2720019
3
-2 -1
-3 -1
-3 -4
1.5811
3
-2 -1
-3 -1
-3 -4
1.5812
4
0 0
1 2
2 4
3 6
3.354101
4
0 0
1 2
2 4
3 6
3.354102
10
37 -84
-93 -93
33 -19
-36 89
-39 -61
-51 -48
-45 30
32 30
-70 -97
-47 9
120.41594
10
37 -84
-93 -93
33 -19
-36 89
-39 -61
-51 -48
-45 30
32 30
-70 -97
-47 9
120.41595
0
I got accepted and my program's output is
Code: Select all
There is no way of packing that polygon.
There is no way of packing that polygon.
There is no way of packing that polygon.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
There is no way of packing that polygon.
There is no way of packing that polygon.
The polygon can be packed in the circle.
Judges input is really weak. It still accepts wrong solutions.
I added in my program case for a single point and added epslion comparision and my program output is now same as
sidky's and
hyperionsshrike's.
Code: Select all
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
There is no way of packing that polygon.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
The polygon can be packed in the circle.