Moderator: Board moderators

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
Ivan Golubev
Experienced poster

Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

simon81
New poster

Posts: 6
Joined: Tue Dec 11, 2001 2:00 am
Location: singapore

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
Wedson
New poster

Posts: 3
Joined: Sun Nov 25, 2001 2:00 am
Location: Brazil

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);
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]
Revenger
Experienced poster

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

a test case

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...)
hlchan
New poster

Posts: 7
Joined: Sat May 25, 2002 8:15 am

My program write the same but it still get WA
Revenger
Experienced poster

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

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
Caesum
Experienced poster

Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK

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
wyvmak
Experienced poster

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

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
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Can the upper answer be accepted by the judge?
yiweya
New poster

Posts: 1
Joined: Thu Aug 08, 2002 6:02 am

Caesum wrote: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
Robbie
New poster

Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

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

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

Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

i got wa too.

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
if n = 0 then halt;
for i := 0 to n - 1 do
begin
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]
lowai
New poster

Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

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

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

Posts: 1
Joined: Thu Nov 13, 2003 3:47 am

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

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm