10005 - Packing polygons

[ahanys]

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?

[10153EN]

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~

[Revenger]

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.

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]

[Revenger]

Maybe I should use another value for Eps? 10e-5 or 10e-15?

[wyvmak]

maybe just "check every triplet of points" is not enough? consider a quadrilateral, with two sides of length sqrt(2)*R+0.1, and two sides of length R/sqrt(3). i guess this quad cannot be packed, but your checking triplet of points will say the contrary

[Revenger]

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.

[wyvmak]

I'm sorry for not expressing well. and I didn't notice integer coordinates. plus I forget all my Pascal, so I cannot verify, but the following test case may fail:

4
100 90
100 110
99 100
111 100
10

I believe the above polygon cannot be packed. Tell me if I'm wrong.

[Revenger]

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.

[arnsfelt]

try this

3
0 1
0 2
0 3
2

[Revenger]

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

[Revenger]

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,V);
MakeOrtogonalVector(V,OV);
L:=Sqrt(R*R-Sqr(Dist(P[a],P)/2));
MakeVectorToLen(OV,L);
PN.X:=(P[a].X+P.X)/2+OV.dX;
PN.Y:=(P[a].Y+P.Y)/2+OV.dY;
ok:=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+P.X)/2-OV.dX;
PN.Y:=(P[a].Y+P.Y)/2-OV.dY;
ok:=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(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!

[arnsfelt]

Ok, I'll help - but I don't really want to read your source code. Insted,
please explain how your algorithm is and try to argue why you think it should work.
(This fits for many other topics as well, by the way)

[Revenger]

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

[arnsfelt]

I'm not sure I understand you. But I'll say this to help you instead:
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.

This ought to translate directly into a simple bruteforce solution. I don't know if it'll be fast enough, though, but I suspect that the test inputs for this problem are rather weak.

[Revenger]

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.