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:

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

:lol:
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. :wink:
The more contests are held, the happier I am.

jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am

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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

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
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am

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
New poster
Posts: 1
Joined: Sun Sep 12, 2004 11:28 pm
Location: Rio Grande-RS/Brazil
Contact:

WRONG JUDGE

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!
SUBMEEEEEEEEEEEEEEEEEETE!

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

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
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

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
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

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
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

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
Sleep enough after death, it is the time to work.
Mostafa Saad

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

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
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

10005 (Polygon Packing) - Need Testing

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

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

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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.. :)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
New poster
Posts: 14
Joined: Fri Aug 13, 2010 12:22 pm

10005-WA

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

Post Reply

Return to “Volume 100 (10000-10099)”