10005 - Packing polygons

[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.

[brianfry713]

Input:

Code: Select all

2
0 0
1 0
0.4
2
0 0
1 0
0.6
0

Correct output:

Code: Select all

There is no way of packing that polygon.
The polygon can be packed in the circle.

[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.

[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.

[lighted]

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.

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.