10005 - Packing polygons

alex[LSD] · Post by **alex[LSD]** » Mon Feb 09, 2004 10:08 am

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.

jamu · Post by **jamu** » Sun Feb 15, 2004 4:51 pm

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 · Post by **sidky** » Thu Mar 18, 2004 6:08 am

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 · Post by **jamu** » Thu Mar 18, 2004 6:14 pm

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 · Post by **genego** » Sun Sep 12, 2004 11:47 pm

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!

yiuyuho · Post by **yiuyuho** » Wed May 04, 2005 1:36 am

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 · Post by **yiuyuho** » Wed May 04, 2005 6:14 am

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 · Post by **chrismoh** » Wed Aug 23, 2006 4:51 am

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 · Post by **898989** » Fri Sep 22, 2006 10:02 pm

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

Darko · Post by **Darko** » Wed Jan 03, 2007 8:46 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 · Post by **LithiumDex** » Fri Apr 20, 2007 3:18 am

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

LithiumDex · Post by **LithiumDex** » Fri Apr 20, 2007 3:52 am

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 · Post by **helloneo** » Wed May 16, 2007 10:02 am

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 · Post by **little joey** » Wed May 16, 2007 11:18 am

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 · Post by **faiem** » Sat Sep 04, 2010 9:47 pm

#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=b-1;
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...

OJ Board

10005 - Packing polygons

WRONG JUDGE

10005 (Polygon Packing) - Need Testing

10005-WA