10005 - Packing polygons

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

hyperionsshrike
New poster
Posts: 1
Joined: Sat Jun 04, 2011 4:40 am

Re: 10005 - Packing Polygons

Post by hyperionsshrike » Sat Jun 04, 2011 5:10 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10005 - Packing Polygons

Post by brianfry713 » Mon Dec 24, 2012 11:32 pm

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.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10005 - Packing Polygons

Post by brianfry713 » Tue Dec 25, 2012 3:21 am

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.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10005 - Packing Polygons

Post by brianfry713 » Tue Dec 25, 2012 8:38 pm

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.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10005 - Packing Polygons

Post by lighted » Sat Aug 02, 2014 4:58 pm

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 100 (10000-10099)”