## 10005 - Packing polygons

**Moderator:** Board moderators

### 10005 - Packing polygons

What's wrong on my solution. I tested all pairs of points and if maximum distance of 2 points is greater then 2*R then I print no else yes. WHAT'S WRONG?

### HI~~

if there exists 2 points the distance between which > 2*R

==> cannot be packed with a circle with radius R

However it seems not necessarily correct in the opposite direction, i.e.

if all the distances between any 2 points <= 2*R not necessarily implies they can be packed by a circle with R

Hope can help~

==> cannot be packed with a circle with radius R

However it seems not necessarily correct in the opposite direction, i.e.

if all the distances between any 2 points <= 2*R not necessarily implies they can be packed by a circle with R

Hope can help~

### 10005 Need help

I use a such algorithm:

1. if N=1 then I write 'The polygon can be packed in the circle.'

2. if N=2 then if Distance between first and second points < 2*R + Epsilon I write ok else I write Not Ok

3. if N>=3 I check every triplet of points. It means that for every 3-angle in polygon I find out Rm (where Rm - is minimum radius of circle in that this 3-angle can be packed) and if Rm>R+Epsilon then I write Not Ok.

[pascal](* Packing polygons *)

Program p10005;

Const MaxN = 100;

Eps = 1E-10;

Message : Array[0..1]of String =

( 'There is no way of packing that polygon.',

'The polygon can be packed in the circle.' );

Type Point = Record X,Y : Integer End;

Var N,i,j,k : Integer;

P : Array[1..MaxN]of Point;

R : Extended;

ok : Byte;

Function Dist(A,B : Point) : Extended;

begin

Dist:=Sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y));

end;

Function GetS(A,B,C : Point) : Extended;

Var s1,s2,s3 : Extended;

begin

s1:=(A.x+B.x)*(A.y-B.y);

s2:=(B.x+C.x)*(B.y-C.y);

s3:=(C.x+A.x)*(C.y-A.y);

GetS:=Abs((s1+s2+s3)/2);

end;

Procedure Check(a1,a2,a3 : Integer);

Var a,b,c,MinR : Extended;

begin

a:=Dist(P[a1],P[a2]);

b:=Dist(P[a2],P[a3]);

c:=Dist(P[a3],P[a1]);

MinR:=a*b*c/4/GetS(P[a1],P[a2],P[a3]);

if MinR>R+Eps then ok:=0;

end;

begin

While True do begin

Read(N);

if N=0 then Break;

for i:=1 to N do Read(P

1. if N=1 then I write 'The polygon can be packed in the circle.'

2. if N=2 then if Distance between first and second points < 2*R + Epsilon I write ok else I write Not Ok

3. if N>=3 I check every triplet of points. It means that for every 3-angle in polygon I find out Rm (where Rm - is minimum radius of circle in that this 3-angle can be packed) and if Rm>R+Epsilon then I write Not Ok.

**But I get WA. Can anybody help me? Please! I really need your help.**[pascal](* Packing polygons *)

Program p10005;

Const MaxN = 100;

Eps = 1E-10;

Message : Array[0..1]of String =

( 'There is no way of packing that polygon.',

'The polygon can be packed in the circle.' );

Type Point = Record X,Y : Integer End;

Var N,i,j,k : Integer;

P : Array[1..MaxN]of Point;

R : Extended;

ok : Byte;

Function Dist(A,B : Point) : Extended;

begin

Dist:=Sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y));

end;

Function GetS(A,B,C : Point) : Extended;

Var s1,s2,s3 : Extended;

begin

s1:=(A.x+B.x)*(A.y-B.y);

s2:=(B.x+C.x)*(B.y-C.y);

s3:=(C.x+A.x)*(C.y-A.y);

GetS:=Abs((s1+s2+s3)/2);

end;

Procedure Check(a1,a2,a3 : Integer);

Var a,b,c,MinR : Extended;

begin

a:=Dist(P[a1],P[a2]);

b:=Dist(P[a2],P[a3]);

c:=Dist(P[a3],P[a1]);

MinR:=a*b*c/4/GetS(P[a1],P[a2],P[a3]);

if MinR>R+Eps then ok:=0;

end;

begin

While True do begin

Read(N);

if N=0 then Break;

for i:=1 to N do Read(P

*.x,P**.y);*

Read(R);

if 2*R+Eps>Dist(P[1],P[2]) then ok:=1 else ok:=0;

if N=1 then ok:=1;

for i:=1 to N-2 do if ok=1 then begin

for j:=i+1 to N-1 do if ok=1 then begin

for k:=j+1 to N do if ok=1 then begin

Check(i,j,k);

end else break;

end else break;

end else break;

Writeln(Message[ok]);

end;

end.[/pascal]Read(R);

if 2*R+Eps>Dist(P[1],P[2]) then ok:=1 else ok:=0;

if N=1 then ok:=1;

for i:=1 to N-2 do if ok=1 then begin

for j:=i+1 to N-1 do if ok=1 then begin

for k:=j+1 to N do if ok=1 then begin

Check(i,j,k);

end else break;

end else break;

end else break;

Writeln(Message[ok]);

end;

end.[/pascal]

### 1005 Why?!!

You say : "consider a quadrilateral, with two sides of length sqrt(2)*R+0.1, and two sides of length R/sqrt(3)". I can not understand your words. If you mean a rectangle with sides sqrt(2)*R+0.1 and R/sqrt(3) then I make that test:

4

0.0 0.0

0.57735 0.0

0.57735 1.5142

0.0 1.5142

1.000

My program write that this polygon can be packed in the circle and it is rigth. Am I rigth? But if you consider not a rectangle why you haven't say anything about angles between sides of quad? Please, make up a test there my algorithm fail.

P.S. In description of problem the coordinates are integers, but my program can also work and with real numbers if change in Point type Integer to Extended. And thanks for your help.

4

0.0 0.0

0.57735 0.0

0.57735 1.5142

0.0 1.5142

1.000

My program write that this polygon can be packed in the circle and it is rigth. Am I rigth? But if you consider not a rectangle why you haven't say anything about angles between sides of quad? Please, make up a test there my algorithm fail.

P.S. In description of problem the coordinates are integers, but my program can also work and with real numbers if change in Point type Integer to Extended. And thanks for your help.

### 1005 You are rigth

You are rigth. There is no way of packing that polygon. And my program write it. But then why it[my program] gets WA? Have you any idea? I haven't. May be something wrong with Judge?

I hope that on the next your test my program will fail but not on previos. And thank you very much for your help.

I hope that on the next your test my program will fail but not on previos. And thank you very much for your help.

### 1005 Thanks

Thank you for this test. You are quite rigth: the points may lie on the same line. At this test my program get Runtime Error on my computer. I change the program in proper way, but Judge Disable and so I can't send my code to it. Then Judge check my solution i shall write about Judge's verdict in the next post

### 10005 Need help

I change my program is so way:

[pascal]Program p10005;

Const MaxN = 100;

Eps = 1E-10;

Message : Array[0..1]of String =

( 'There is no way of packing that polygon.',

'The polygon can be packed in the circle.' );

Type Point = Record X,Y : Extended End;

Vector = Record dX,dY : Extended End;

Var N,i,j : Integer;

P : Array[1..MaxN]of Point;

R : Extended;

ok : Byte;

Function Dist(A,B : Point) : Extended;

begin

Dist:=Sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y));

end;

Procedure MakeVectorByPoints(A,B : Point; Var C : Vector);

begin

C.dX:=A.X-B.X;

C.dY:=A.Y-B.Y;

end;

Procedure MakeOrtogonalVector(V : Vector; Var NewV : Vector);

begin

NewV.dX:=-V.dY;

NewV.dY:=V.dX;

end;

Procedure MakeVectorToLen(Var V : Vector; Len : Extended);

Var CurLen,J : Extended;

begin

CurLen:=Sqrt(V.dX*V.dX+V.dY*V.dY);

J:=Len/CurLen;

V.dX:=V.dX*J;

V.dY:=V.dY*J;

end;

Procedure Check(a,b : Integer);

Var V,OV : Vector;

L : Extended;

PN : Point;

i : Integer;

begin

MakeVectorByPoints(P[a],P

[pascal]Program p10005;

Const MaxN = 100;

Eps = 1E-10;

Message : Array[0..1]of String =

( 'There is no way of packing that polygon.',

'The polygon can be packed in the circle.' );

Type Point = Record X,Y : Extended End;

Vector = Record dX,dY : Extended End;

Var N,i,j : Integer;

P : Array[1..MaxN]of Point;

R : Extended;

ok : Byte;

Function Dist(A,B : Point) : Extended;

begin

Dist:=Sqrt(Sqr(A.x-B.x)+Sqr(A.y-B.y));

end;

Procedure MakeVectorByPoints(A,B : Point; Var C : Vector);

begin

C.dX:=A.X-B.X;

C.dY:=A.Y-B.Y;

end;

Procedure MakeOrtogonalVector(V : Vector; Var NewV : Vector);

begin

NewV.dX:=-V.dY;

NewV.dY:=V.dX;

end;

Procedure MakeVectorToLen(Var V : Vector; Len : Extended);

Var CurLen,J : Extended;

begin

CurLen:=Sqrt(V.dX*V.dX+V.dY*V.dY);

J:=Len/CurLen;

V.dX:=V.dX*J;

V.dY:=V.dY*J;

end;

Procedure Check(a,b : Integer);

Var V,OV : Vector;

L : Extended;

PN : Point;

i : Integer;

begin

MakeVectorByPoints(P[a],P

**,V);**

MakeOrtogonalVector(V,OV);

L:=Sqrt(R*R-Sqr(Dist(P[a],PMakeOrtogonalVector(V,OV);

L:=Sqrt(R*R-Sqr(Dist(P[a],P

**)/2));**

MakeVectorToLen(OV,L);

PN.X:=(P[a].X+PMakeVectorToLen(OV,L);

PN.X:=(P[a].X+P

**.X)/2+OV.dX;**

PN.Y:=(P[a].Y+PPN.Y:=(P[a].Y+P

**.Y)/2+OV.dY;**

ok:=1;

for i:=1 to N do

if Dist(Pok:=1;

for i:=1 to N do

if Dist(P

*,PN)>R+Eps then ok:=0;*

if ok=0 then begin

PN.X:=(P[a].X+Pif ok=0 then begin

PN.X:=(P[a].X+P

**.X)/2-OV.dX;**

PN.Y:=(P[a].Y+PPN.Y:=(P[a].Y+P

**.Y)/2-OV.dY;**

ok:=1;

for i:=1 to N do

if Dist(Pok:=1;

for i:=1 to N do

if Dist(P

*,PN)>R+Eps then ok:=0;*

end;

end;

begin

While True do begin

Read(N);

if N=0 then Break;

for i:=1 to N do Read(Pend;

end;

begin

While True do begin

Read(N);

if N=0 then Break;

for i:=1 to N do Read(P

*.x,P**.y);*

Read(R);

if N=1 then ok:=1;

for i:=1 to N-1 do if ok=0 then begin

for j:=i+1 to N do if ok=0 then begin

Check(i,j);

end else break;

end else break;

Writeln(Message[ok]);

end;

end.[/pascal]

But I also get WA Heeeelp me! Pleeeease!Read(R);

if N=1 then ok:=1;

for i:=1 to N-1 do if ok=0 then begin

for j:=i+1 to N do if ok=0 then begin

Check(i,j);

end else break;

end else break;

Writeln(Message[ok]);

end;

end.[/pascal]

But I also get WA Heeeelp me! Pleeeease!

### 10005 Algorithm

Well, I check all pairs of points for:

1. If d(Point1,Point2)>2R then I write no else

2. I find Point3 so that d(Point3,Point1)=d(Point3,Point2)=R

3. Then if there is no such PointX that d(Point3,PointX)>R I write ok else

4. I find another Point4 so that d(Point4,Point1)=d(Point4,Point2)=R

5. Then if there is no such PointX that d(Point4,PointX)>R I write ok else I go to the next pair.

If for all pairs I didn't find the PointY (the center of circle) I write no.

In other words my algorithm is such: try to find such two points that lies on the border of circle in that polygon had to be packed.

I hope that you'll understand me. Sorry for my English

1. If d(Point1,Point2)>2R then I write no else

2. I find Point3 so that d(Point3,Point1)=d(Point3,Point2)=R

3. Then if there is no such PointX that d(Point3,PointX)>R I write ok else

4. I find another Point4 so that d(Point4,Point1)=d(Point4,Point2)=R

5. Then if there is no such PointX that d(Point4,PointX)>R I write ok else I go to the next pair.

If for all pairs I didn't find the PointY (the center of circle) I write no.

In other words my algorithm is such: try to find such two points that lies on the border of circle in that polygon had to be packed.

I hope that you'll understand me. Sorry for my English

You should realize the following facts:

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

### 10005 Thanks

I do the same as you say but my program get WA. Is there some special tests? Or can you give me a good test? Thanks.