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

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

10005 - Packing polygons

Post by ahanys » Fri May 17, 2002 11:41 am

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

HI~~

Post by 10153EN » Fri May 17, 2002 4:31 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10005 Need help

Post by Revenger » Mon Jun 10, 2002 2:06 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10005

Post by Revenger » Sun Jun 16, 2002 11:07 am

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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sun Jun 16, 2002 4:01 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

1005 Why?!!

Post by Revenger » Sun Jun 16, 2002 7:15 pm

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Mon Jun 17, 2002 3:50 am

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

1005 You are rigth

Post by Revenger » Mon Jun 17, 2002 6:31 am

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 :wink: but not on previos. And thank you very much for your help.

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Mon Jun 17, 2002 10:18 am

try this

3
0 1
0 2
0 3
2

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

1005 Thanks

Post by Revenger » Mon Jun 17, 2002 11:23 am

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10005 Need help

Post by Revenger » Mon Jun 17, 2002 7:54 pm

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 :cry: Heeeelp me! Pleeeease!

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Mon Jun 17, 2002 8:04 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10005 Algorithm

Post by Revenger » Tue Jun 18, 2002 4:27 pm

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

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Wed Jun 19, 2002 10:28 pm

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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10005 Thanks

Post by Revenger » Thu Jun 20, 2002 11:18 am

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.

Post Reply

Return to “Volume 100 (10000-10099)”