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

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact: THANKS! That was very stupid of me. I just never realized that I dont have to find the minimum radius, putting them in a circle with radius R is enough. Well sometimes I just make my life harder than it needs to be.
Anyways, now I can say I understood. Thanks again, man. The more contests are held, the happier I am.

jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am
Can anyone who got accepted confirm this input/output?

input:
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
output:
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.
There is no way of packing that polygon.
The polygon can be packed in the circle.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
Here's my Output:
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.

jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am
argh! stupid bug in the code which given coordinates of three non-colinear points finds the center of the circle passing through them...

thanks for help

genego
New poster
Posts: 1
Joined: Sun Sep 12, 2004 11:28 pm
Location: Rio Grande-RS/Brazil
Contact:

WRONG JUDGE

HEY, look at my code:

[c]
#include <stdio.h>
#include <math.h>
#define sqr(A) ((A)*(A))
main()
{
long n, i,xp,yp,x,y;
double r, xc, yc;

while (scanf ("%d\n",&n))
{
if (n==0) break;
scanf ("%ld %ld\n",&x,&y);
for (xc=x,yc=y,i=1;i<n;i++) {
scanf ("%ld %ld\n",&xp,&yp);
xc+=xp; yc+=yp;
}
xc/=n; yc/=n;
scanf ("%lf\n",&r);
if (sqrt (sqr(xc-x) + sqr(yc-y)) <= r)
printf ("The polygon can be packed in the circle.\n");
else
printf ("There is no way of packing that polygon.\n");
}
}
[/c]

I've submitted and got AC. in 0.000 seconds.
It proves that the judge inputs are very simple. For the case prompted, my program gives this output:
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.
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.
which is wrong!
SUBMEEEEEEEEEEEEEEEEEETE!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
ye, thanks horape, very good point there.

But, I am wondering what do I have to do to find the minimum R? Do I have to use bisection aparted with this solution to the descision problem? Are there better ways?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
I actually used revenger's algorithm and got AC.

He must have bug in the code that does not correspond to the main frame of his algorithm.

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
And over a year later...

I assume below that all circles have 3 points on the boundary, thus ignoring > 3 points and the case where there are 2 points on the minimal circle's boundary (in this case the 2 points are on the diameter).

To find minimal R, O(n^3) is hard to beat. Simply take all possible pairs of points and find the third point that makes the smallest angle with the line connecting the two points. Then check if all points are enclosed in that circle.

If you like randomization, there's an expected O(n) time solution.

Suppose you knew one of the points on the circle. You can find the other two in expected O(n) time in the following way:

Start with an empty set. Insert points randomly into the set. Let the first two points inserted define the other points in the circle (assuming not collinear). Then for every subsequent point inserted into the set, do the following:

(1) If point is in the circle, ok and good.
(2) If point is not in the circle, take it as a second point and find a third point from the set as the third point in the circle. (Why does this work? - it's not that trivial to show)

So step (2) takes O(n) time, where n is the number of elements in the set. But we don't always run step (2). The probability of running step 2 in the xth insertion is at most 2/x, since there are at most two other points in the defining boundary of the circle surrounding all the points in the set.

Then the expected time becomes linear.

So the question is - now if you know *none* of the points on the circle, how do you find the points in expected linear time?

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
I got it is 0.000s
Note, to pack some object in another, make them have the same center.

This is the procedure
1)Get convex Hull
2)Find C = the center of convex Hull(See problem 10002)
3)Iterate on all points oh Hull then

Code: Select all

For(All points in hull)
if( dis(C, convex[i]) > r)
Fail

if pass all points -->Suceed;
Try to think about the validation of algorithm
Sleep enough after death, it is the time to work.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

10005 (Polygon Packing) - Need Testing

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

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:
Solved it, my AC program now produces:

Code: Select all

The polygon can be packed in the circle.
There is no way of packing that polygon.
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.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
The polygon can be packed in the circle.
Anyone care to compare?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Hello..~
What is the correct algorithm to solve this problem..?
I tried to find the convex hull and find the center of mass of it..
But it doesn't seem to work.. (don't get a correct answer for the sample above)
Can anybody help me..?

Thanks.. little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I'll try to explain my method.

For any set of points in the plane, there is exactly one smallest circle that encloses them all. Let this circle have radius minr. We also know that at least two of the points should lie on the boundary of the circle. Now consider a bigger circle with radius r > minr with the same center. Because this circle is bigger, none of the points will be on the boundary. We can, however, move this circle in the plane until at least two points are on its boundary and all other points are within the circle (this can be done in many ways).

So, to solve this problem, we look for two points from the original set, on the boundary of a circle with radius r, while all other points lie within the circle. If such a pair of points can be found, the answer to this problem is yes. This leads to a straight forward O(n^3) algorithm:

Code: Select all

for all pairs of points in the original set:
if their distance is bigger than 2*r goto impossible
else if their distance is equal to 2*r:
form a circle through these points and check if all other points lie within this circle
if they do goto possible
else goto impossible
else (their distance is smaller than 2*r):
form the two circles through these points; for both circles check if all other points lie within it
if for any one of them they do, goto possible
else continue to the next pair
if, after searching all pairs, no jump to possible is made, goto impossible
Note 1: if two points are less than 2*r apart, two circles can be constructed, one with the center 'above' the connecting line, and one with the center 'below' the connecting line.

Note 2: If you give it some thought, you can reduce the number of pairs to consider thereby making the method faster. For the given input, however, the given method is fast enough: my program runs in 0.002 seconds.

Hope it helps.

faiem
New poster
Posts: 14
Joined: Fri Aug 13, 2010 12:22 pm

10005-WA

#include<stdio.h>
#include<math.h>

double a,b,i,j,k,m,p,c=0, l,r;

main()
{

while(scanf("%lf",&b)==1)
{
if(b==0)
break;

c=0;
for(i=1;i<=b;i++)
for(j=0;j<2;j++)
scanf("%lf",&a[j]);
scanf("%lf",&r);
r=r*2;

p=b-1;
m=2;
for(i=1;i<b;i++)
{
k=m;
for(j=p;j>=1;j--)
{
l=((a-a[k])*(a-a[k]));

l=l+((a-a[k])*(a-a[k]));

l=sqrt(l);

if(l>r)
{
i=b;c=1;
break;
}

k++;
}
m++;p--;
}

if(c==0)
printf("The polygon can be packed in the circle.\n");
else
printf("There is no way of packing that polygon.\n");
}
return 0;
}

My code is here.
Plz give some test case...