10005 - Packing polygons

[Revenger]

You wrote

1. Given two points the unique minimal radius circle intersecting these is the circle with center in the middle and half the distance as radius.

Can you explain it to me on example

[arnsfelt]

I believe your programs does not do what I said...

[oracle]

• 1. Given two points the unique minimal radius circle intersecting these is the circle with center in the middle and half the distance as radius.
  
  2. Given three points that are not colinear there is a unique circle that intersect these.
  
  3. Given n>1 points it it possible to choose two or three points such that the minimal circle including all the points is as descriped above.

Do you think the above algorithm is correct. Have anyone using that algorithm got ACCEPTED SUBMITION ?.

[Dominik Michniewski]

Could anyone help me and posts counterexample, in which my algorithm fails ?

Code: Select all

EPS ==> 1e-9
N - number of points in polygon

		R *= 2.0; /* diameter of circle */
		max = 0.0;
		for(i=0;i<N;i++)
			for(j=i+1;j<N;j++)
			{
				x = points[i][0] - points[j][0];
				y = points[i][1] - points[j][1];
                                                                tmp = x*x + y*y;
				if(tmp > max) max = tmp;
			}
		max = sqrt(max) + EPS;
		if(max <= R)
			printf("The polygon can be packed in the circle.\n");
		else
			printf("There is no way of packing that polygon.\n");

[Adrian Kuegel]

3
0 0
0 4
3 2
2.0
0

I think you will print that it is possible to pack that polygon, but it is not.

[Dominik Michniewski]

Thanks Adrian for this input ....
I have to think deeper about this problem ....

Dominik

[Eddy]

This is my code:
{ @JUDGE_ID: 27272HH 10005 Pascal "Packing polygons" }
Program p10005 (input,output);
var x,y:array[1..200] of integer;
n,i,maxX,maxY,minX,minY:integer;
r:real;

Procedure Solve;
var centerX,centerY,distance:real;
result:boolean;
i:integer;
Begin
{A1(minX,maxY),A2(maxX,maxY),A3(maxX,minY),A4(minX,minY)}
result:=true;
centerX:=(maxX+minX)/2;
centerY:=(maxY+minY)/2;
for i:=1 to n do
Begin
distance:=sqrt(sqr(x-centerx)+sqr(y-centerY));
if distance>r then
Begin
result:=false;break;
End;
End;
if result=true then
writeln('The polygon can be packeg in the circle.')
else writeln('There is no way the packing of polygon.');
End;

BEGIN
readln(n);
while n<>0 do
Begin
maxX:=-32768;maxY:=-32768;
minX:=32767;minY:=32767;
for i:=1 to n do
Begin
readln(x,y);
if x>maxX then maxX:=x;
if x<minX then minX:=x;
if y>maxY then maxY:=y;
if y[i]<minY then minY:=y[i];
End;
readln(r);
solve;
readln(n);
End;
END.

The Judge system reported "Wrong Answer".
Help Me.
Thanks![pascal][/pascal]

[Eddy]

This is my code:
{ @JUDGE_ID: 27272HH 10005 Pascal "Packing polygons" }
Program p10005 (input,output);
var x,y:array[1..200] of integer;
n,i,maxX,maxY,minX,minY:integer;
r:real;

Procedure Solve;
var centerX,centerY,distance:real;
result:boolean;
i:integer;
Begin
{A1(minX,maxY),A2(maxX,maxY),A3(maxX,minY),A4(minX,minY)}
result:=true;
centerX:=(maxX+minX)/2;
centerY:=(maxY+minY)/2;
for i:=1 to n do
Begin
distance:=sqrt(sqr(x-centerx)+sqr(y-centerY));
if distance>r then
Begin
result:=false;break;
End;
End;
if result=true then
writeln('The polygon can be packeg in the circle.')
else writeln('There is no way the packing of polygon.');
End;

BEGIN
readln(n);
while n<>0 do
Begin
maxX:=-32768;maxY:=-32768;
minX:=32767;minY:=32767;
for i:=1 to n do
Begin
readln(x,y);
if x>maxX then maxX:=x;
if x<minX then minX:=x;
if y>maxY then maxY:=y;
if y[i]<minY then minY:=y[i];
End;
readln(r);
solve;
readln(n);
End;
END.

The Judge system reported "Wrong Answer".
Help Me.
Thanks![pascal][/pascal]

[superraskao]

I get WA with this code, can anyone help?

[c]
#include <stdio.h>
#include <math.h>

float X[100];
float Y[100];
int N;
float M[2][3];

float tc[2];


void resolver()
{
float c;
float * F1;
float * F2;

F1 = M[0];
F2 = M[1];
if(M[0][0] == 0)
{
F1 = M[1];
F2 = M[0];
}
else
{
c = M[1][0]/M[0][0];
M[1][1] = M[1][1] - M[0][1]*c;
M[1][2] = M[1][2] - M[0][2]*c;
}
tc[1] = F2[2] / F2[1];
tc[0] = (F1[2] - (tc[1]*F1[1]))/F1[0];
}

float cruz(int a, int b, int c)
{
return((X[a]-X[c]) * (Y - Y[c]) - (X-X[c]) * (Y[a] - Y[c]));
}

float distancia(int i, float x, float y)
{
float xd,yd;
xd = (x - X);
yd = y - Y;

return(xd*xd + yd*yd);
}

int contiene(float x, float y, float r)
{

int i;
double r2;
r2 = r*r;

for(i = 0; i < N; i++)
{
if(distancia(i,x,y) > r)
{

return 0;
}
}
return 1;
}

int puede(float r)
{
int i, j, k;
float rt, xt, yt;
for(i = 0; i < N; i++)
{
for(j = i+1; j < N; j++)
{
xt =(X + X[j])/2;
yt =(Y + Y[j])/2;
rt = distancia(i,X[j],Y[j])/4;

if(contiene(xt,yt,rt))
{
if(r >= rt)
{
return(1);
}
}
for(k = j+1; k < N; k++)
{
if(cruz(i,j,k) != 0)
{
M[0][0] = 2*(X[k] - X);
M[0][1] = 2*(Y[k] - Y);
M[0][2] = Y[k]*Y[k] + X[k]*X[k] - X*X - Y*Y;
M[1][0] = 2*(X[j] - X[i]);
M[1][1] = 2*(Y[j] - Y[i]);
M[1][2] = Y[j]*Y[j] + X[j]*X[j] - X[i]*X[i] - Y[i]*Y[i];

resolver();
rt = distancia(i,tc[0],tc[1]);
xt = tc[0];
yt = tc[1];


if(contiene(xt,yt,rt))
{
if(r >= rt)
{
return(1);
}
}
}


}


}
}
return(0);
}

main()
{
float r;
int p,i;
freopen("p10005.in", "r", stdin);
scanf("%d",&N);

while(N > 0)
{
for(i = 0; i < N; i++)
{
scanf("%f %f",&X[i],&Y[i]);

}
scanf("%f",&r);

p = 0;
if(N > 1)
{
p = puede(r);
}
else
p = 1;
if(p)
printf("The polygon can be packed in the circle.\n");
else
printf("There is no way of packing that polygon.\n");
scanf("%d",&N);


}
}


[/c]

[alex[LSD]]

The thing is - My solution is N^3. I am #326 of 331 in the promlems list with 1.68s.
So please, enlighten my butt, tell me about how to solve it fast.
P.S. I d really appreciate that.

[horape]

The thing is - My solution is N^3. I am #326 of 331 in the promlems list with 1.68s.
So please, enlighten my butt, tell me about how to solve it fast.
P.S. I d really appreciate that.

My solution is O(N^3) too, and runs on 0.004 seconds.

For each pair of points i calc the circle of radius R that has that pair of points on the perimeter, and then test inclusion of all the
points on that circle.

Saludos,
HoraPe

[alex[LSD]]

Horape I dont get what do you mean by "test".
I also went through all the pairs, and for each pair I found the MINIMUM ANGLE from a 3rd point to the line segment. I needed minimum angles for two cases separately : for "above" the line segment and for "below". Did you do smth like this? I guess my GetAngle() was too time-consuming...

[horape]

Horape I dont get what do you mean by "test".
I also went through all the pairs, and for each pair I found the MINIMUM ANGLE from a 3rd point to the line segment. I needed minimum angles for two cases separately : for "above" the line segment and for "below". Did you do smth like this? I guess my GetAngle() was too time-consuming...

Hmmm, for each pair of points I get the center of the circle of radius R that has them on the perimeter. Simple geometry:

Code: Select all

ab = b-a; // vector
abp = perp(ab); // perp (x,y) = (y,-x)

d = dist(a,b)
if (d>2*R)
   there is no way for a circle of radius R to include both points.
// dp

[alex[LSD]]

Sounds like binary search.
So where do you get the R value? And why dont you go both directions from middle of AB?

[horape]

Sounds like binary search.
So where do you get the R value? And why dont you go both directions from middle of AB?

It isn't binary search, nor something like that, as far as i understand. I test each pair of vertices, and then test it again every vertex.

The last line of the input case will be a real number indicating the radius R of the circle.

And I do AB and BA, that's why I just choose one of the points and not both.

Saludos,
HoraPe