10005  Packing polygons
Moderator: Board moderators

 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.
Can anyone who got accepted confirm this input/output?
input:
input:
output: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
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.

 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.

 New poster
 Posts: 1
 Joined: Sun Sep 12, 2004 11:28 pm
 Location: Rio GrandeRS/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(xcx) + sqr(ycy)) <= 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:
[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(xcx) + sqr(ycy)) <= 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:
which is wrong!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.
SUBMEEEEEEEEEEEEEEEEEETE!
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?
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?

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) 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
Try to think about the validation of algorithm
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;
Sleep enough after death, it is the time to work.
Mostafa Saad
Mostafa Saad
Well, otput of my AC program is:
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.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.

 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
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
 Chris Adams

 New poster
 Posts: 44
 Joined: Tue Jun 06, 2006 6:44 pm
 Location: Nova Scotia, Canada
 Contact:
Solved it, my AC program now produces:
Anyone care to compare?
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.
 Chris Adams

 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:
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.
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 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.
10005WA
#include<stdio.h>
#include<math.h>
double a[101][2],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=b1;
m=2;
for(i=1;i<b;i++)
{
k=m;
for(j=p;j>=1;j)
{
l=((a[0]a[k][0])*(a[0]a[k][0]));
l=l+((a[1]a[k][1])*(a[1]a[k][1]));
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...
#include<math.h>
double a[101][2],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=b1;
m=2;
for(i=1;i<b;i++)
{
k=m;
for(j=p;j>=1;j)
{
l=((a[0]a[k][0])*(a[0]a[k][0]));
l=l+((a[1]a[k][1])*(a[1]a[k][1]));
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...