OJ Board

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.

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.

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.

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

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!

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?

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.

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

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.

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

Solved it, my AC program now produces:
Anyone care to compare?

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

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.

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