P218 Moth Eradication

[Ivan Golubev]

As I can understand it's simple problem -- only to compute convex hull. But there're couple tricks, with collinear points and when number of points less than 3. Is this input/output correct? Or this problem has another tricks?

Input:
6
0 0
1 1
2 2
3 3
0 3
1 2
1
5 5
2
1 1
5 6
0

Region #1:
(0.0,3.0)-(3.0,3.0)-(2.0,2.0)-(1.0,1.0)-(0.0,0.0)-(0.0,3.0)
Perimeter length = 10.24

Region #2:
(5.0,5.0)-(5.0,5.0)
Perimeter length = 0.00

Region #3:
(1.0,1.0)-(5.0,6.0)-(1.0,1.0)
Perimeter length = 12.81

[simon81]

huh..i'm also puzzled about this.
hope anyone can answer

[Wedson]

I got the following output (for the given input) from my program, which was accepted:

Region #1:
(0.0,0.0)-(0.0,3.0)-(3.0,3.0)-(2.0,2.0)-(1.0,1.0)-(0.0,0.0)
Perimeter length = 10.24

Region #2:
(5.0,5.0)-(5.0,5.0)
Perimeter length = 0.00

Region #3:
(1.0,1.0)-(5.0,6.0)-(1.0,1.0)
Perimeter length = 12.81

[Revenger]

My program gets WA ( But on all my tests it's correct. Can anybody help me?

[pascal]Program p218;

Const MaxN = 1000;

Type Point = record X,Y : Extended end;

Var N,i,B,Pred,j,ii,t : Integer;
P : array[1..MaxN]of Point;
Use : array[1..MaxN]of byte;
Order : array[0..MaxN]of Integer;
Ans : Extended;

Function Higher(Num1,Num2,Num3 : Point) : byte;
Var w1,w2 :extended;
x1,y1,x2,y2,x3,y3 :extended;
Begin
x1:=num1.X;
x2:=num2.X;
x3:=num3.X;
y1:=num1.Y;
y2:=num2.Y;
y3:=num3.Y;
w1:=(x1-x2)*(y3-y1);
w2:=(x3-x1)*(y1-y2);
if w1>w2 then Higher:=1 else
if w1<w2 then Higher:=0 else
Higher:=2;
end;

Function Dist(A,B : Point) : Extended;
Var E : Extended;
begin
E:=(A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y);
Dist:=sqrt(E);
end;

Function GetDist(P1,P2 : Integer) : Extended;
begin
GetDist:=Dist(P[P1],P[P2]);
end;

Function Check(P1,P2 : Integer) : boolean;
Var u,P3 : Integer;
begin
Check:=false;
u:=-1;
for P3:=1 to N do
if (P3<>P1)and(P3<>P2) then begin
if (u=-1)or(u=2) then u:=Higher(P[P1],P[P2],P[P3]) else
if (Higher(P[P1],P[P2],P[P3])<>u)and
(Higher(P[P1],P[P2],P[P3])<>2) then exit;
end;
Check:=true;
end;

begin
t:=0;
While True Do begin
FillChar(Use,SizeOf(Use),0);
Read(N);
if N=0 then Break;
t:=t+1;
for i:=1 to N do read(P[i].X,P[i].Y); B:=1;
for i:=2 to N do if P[i].X<P[B].X then B:=i;
Pred:=B; Use[B]:=1; Ans:=0;
Order[1]:=B;
Order[0]:=1;
While True do begin
j:=-1;
for ii:=1 to N do begin
i:=Pred+ii; if i>N then i:=i-N;
if Use[i]=0 then
if Check(Pred,i) then begin
if j=-1 then begin
j:=i;
Inc(Order[0]);
Order[Order[0]]:=i;
end else
if Dist(P[Order[0]-1],P[Order[0]]) >
Dist(P[Order[0]-1],P[i]) then begin
j:=i;
Order[Order[0]]:=i;
end;
end;
end;
if j=-1 then begin
Ans:=Ans+GetDist(Pred,B);
break;
end;
Use[j]:=1;
Ans:=Ans+GetDist(Pred,j);
Pred:=j;
end;
if t>1 then Writeln;
Writeln('Region #',t:0,':');
B:=-1;
if Order[0]>2 then
if Higher(P[Order[1]],P[Order[2]],P[Order[Order[0]]])=1 then
B:=1;
if B=1 then begin
for i:=1 to Order[0] do begin
Write('(',P[Order[i]].x:0:1,',');
Write(P[Order[i]].y:0:1,')-');
end;
Write('(',P[Order[1]].x:0:1,',');
Writeln(P[Order[1]].y:0:1,')');
end else begin
Write('(',P[Order[1]].x:0:1,',');
Write(P[Order[1]].y:0:1,')-');
for i:=Order[0] downto 1 do begin
Write('(',P[Order[i]].x:0:1,',');
Write(P[Order[i]].y:0:1,')');
if i=1 then Writeln else Write('-');
end;
end;
Write('Perimeter length = ');
Writeln(Ans:0:2);
end;
end.[/pascal]

[hlchan]

Try this test case:

9
0 1
5 0
4 1.5
3 -0.2
0 -1
2.5 -1.5
0 0
2 2
6 0
0

This should give probably:

Region #1:
(0.0,1.0)-(2.0,2.0)-(4.0,1.5)-(6.0,0.0)-(2.5,-1.5)-(0.0,-1.0)-(0.0,0.0)-(0.0,1.0)
Perimeter length = 15.16


Also, it seems that there is no cases for number of point <= 2 (i use the code: if( number<=2) while( true ) cout << "haha";, and see if i got time limit exceed error...)

[Revenger]

My program write the same but it still get WA

[Caesum]

I'm also having difficultly with WA but correct answers for test cases and examples given here. Can anyone confirm the output for:

3
1 1
1 2
1 3
0

is


Region #1:
(1.0,1.0)-(1.0,2.0)-(1.0,3.0)-(1.0,2.0)-(1.0,1.0)
Perimeter length = 4.00

[wyvmak]

my program would output:

Region #1:
(1.0,1.0)-(1.0,3.0)-(1.0,2.0)-(1.0,1.0)
Perimeter length = 4.00

[..]

But........my program output this........

Region #1:
(1.0,1.0)-(1.0,2.0)-(1.0,3.0)-(1.0,2.0)-(1.0,1.0)
Perimeter length = 4.00

[yiweya]

Can the upper answer be accepted by the judge?

[Robbie]

I'm also having difficultly with WA but correct answers for test cases and examples given here. Can anyone confirm the output for:

3
1 1
1 2
1 3
0

is


Region #1:
(1.0,1.0)-(1.0,2.0)-(1.0,3.0)-(1.0,2.0)-(1.0,1.0)
Perimeter length = 4.00

Rep:
I think there won't be any test like this

[Even]

all the case above I get the reasonable answer...

but still WA...can you give me more test case???

[lowai]

very confused.

[pascal]
const
maxn = 100;
type
tpoint = record
x, y : real;
end;
var
n, top, caseno : integer;
list : array[0..maxn]of tpoint;
stk : array[1..maxn]of integer;

procedure swap(var a, b : tpoint);
var t : tpoint;
begin
t := a; a := b; b := t;
end;

function multi(var p1, p2, p0 : tpoint) : real;
begin
multi := (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
end;

function comp(var p1, p2 : tpoint) : boolean;
var t : real;
begin
t := multi(p1, p2, list[0]);
if (t > 0) or (t = 0) and
(sqr(p1.x - list[0].x) + sqr(p1.y - list[0].y) <
sqr(p2.x - list[0].x) + sqr(p2.y - list[0].y)) then
comp := true
else
comp := false;
end;

procedure sort(p, r : integer);
var i, j : integer;
x : tpoint;
begin
if r - p + 1 <= 5 then
begin
for j := p + 1 to r do
begin
i := j;
while(i > 1) and comp(list[i], list[i - 1]) do
begin
swap(list[i], list[i - 1]);
dec(i);
end;
end;
end
else
begin
x := list[(p + r) div 2];
i := p;
j := r;
repeat
while comp(list[i], x) do inc(i);
while comp(x, list[j]) do dec(j);
if i < j then swap(list[i], list[j]);
until i >= j;
sort(p, j);
sort(i + 1, r);
end;
end;

procedure init;
var i : integer;
begin
readln(n);
if n = 0 then halt;
for i := 0 to n - 1 do
begin
readln(list[i].x, list[i].y);
if (list[i].y < list[0].y) or (list[i].y = list[0].y) and
(list[i].x < list[0].x) then swap(list[0], list[i]);
end;
sort(1, n - 1);
end;

procedure graham;
var i : integer;
ans : real;
begin
for i := 1 to 3 do stk[i] := i - 1;
top := 3;
for i := 3 to n - 1 do
begin
while (top > 1) and (multi(list[i], list[stk[top]], list[stk[top - 1]]) >= 0) do
dec(top);
inc(top);
stk[top] := i;
end;
writeln('Region #', caseno, ':');
ans := 0;
write('(', list[stk[1]].x : 0 : 1, ',', list[stk[1]].y : 0 : 1, ')');
for i := 2 to top do
begin
write('-(', list[stk[i]].x : 0 : 1, ',', list[stk[i]].y : 0 : 1, ')');
ans := ans + sqrt(sqr(list[stk[i]].x - list[stk[i - 1]].x) + sqr(list[stk[i]].y - list[stk[i - 1]].y));
end;
writeln('-(', list[stk[1]].x : 0 : 1, ',', list[stk[1]].y : 0 : 1, ')');
ans := ans + sqrt(sqr(list[stk[top]].x - list[stk[1]].x) + sqr(list[stk[top]].y - list[stk[1]].y));
writeln('Perimeter length = ',ans : 0 : 2);
end;

procedure outspecial;
var ans : real;
begin
writeln('Region #', caseno, ':');
write('(', list[0].x : 0 : 1, ',', list[0].y : 0 : 1, ')');
writeln('-(', list[1].x : 0 : 1, ',', list[1].y : 0 : 1, ')');
ans := sqrt(sqr(list[1].x - list[0].x) + sqr(list[1].y - list[0].y));
writeln('Perimeter length = ',ans : 0 : 2);
end;

begin
caseno := 0;
while true do
begin
inc(caseno);
init;
if caseno > 1 then writeln;
if n > 2 then graham else outspecial;
end;
end.
[/pascal][/pascal]

[cantisan]

Can you please send me the code to solve Moth Eradication ?

[sclo]

There's no need to get fancy here, and there are no tricky cases. This problem should be solved easily with prewritten codes. If your convex hull code can output in clockwise order including the collinear points, then it should get AC. Otherwise, consider rewriting the convex hull code, there's probably something wrong with the convex hull code.