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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
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
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:
I believe your programs does not do what I said...

oracle
New poster
Posts: 4
Joined: Tue Sep 17, 2002 6:21 pm
arnsfelt 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.

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### 10005 - Packing polygons ...

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] - points[j];
y = points[i] - points[j];
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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Thanks Adrian for this input ....
I have to think deeper about this problem ....

Dominik

Eddy
New poster
Posts: 2
Joined: Sun Dec 22, 2002 6:47 am
Contact:

### 10005-Wrong Answer-Help me

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
New poster
Posts: 2
Joined: Sun Dec 22, 2002 6:47 am
Contact:

### 10005-Wrong Answer-Help me

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
New poster
Posts: 1
Joined: Wed May 28, 2003 10:10 pm

### 10005

I get WA with this code, can anyone help?

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

float X;
float Y;
int N;
float M;

float tc;

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

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

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 = 2*(X[k] - X);
M = 2*(Y[k] - Y);
M = Y[k]*Y[k] + X[k]*X[k] - X*X - Y*Y;
M = 2*(X[j] - X[i]);
M = 2*(Y[j] - Y[i]);
M = Y[j]*Y[j] + X[j]*X[j] - X[i]*X[i] - Y[i]*Y[i];

resolver();
rt = distancia(i,tc,tc);
xt = tc;
yt = tc;

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]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

### 10005 (Packing Polygons) VERY fast solutions

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

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

### Re: 10005 (Packing Polygons) VERY fast solutions

alex[LSD] wrote: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]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
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...
The more contests are held, the happier I am.

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
alex[LSD] wrote: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]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:
Sounds like binary search.
So where do you get the R value? And why dont you go both directions from middle of AB?
The more contests are held, the happier I am.

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
alex[LSD] wrote: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