218 - Moth Eradication

[simon81]

I keep getting W.A for this problme.
Could somebody clear my following doubts:
1) If there is only 1 point, say,, (0,, 0)
what should the output be?
2) If all the input points are collinear,
say (1, 0), (2, 0), (3, 0), (4, 0)
what should the output be?

thanks a lot!

[Casimiro]

In this problem you must find the Convex Hull, but you must consider co-linear points.
So, if you have an input which is formed only by colinear points, all of them will be in the Hull. If the input has only one point, the Hull will be itself.
Notice that even if you have a polygon (let's say a rectangle) but there are colinear points in some side (possibly more than one), you must output all of them.

Best Regards, Casimiro.

[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.X,P.Y); B:=1;
for i:=2 to N do if P.X<P.X then B:=i;
Pred:=B; Use:=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=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) 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].x:0:1,',');
Write(P[Order].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].x:0:1,',');
Write(P[Order].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

[obayashi]

i try to use graham scan to solve this prob. but get WA...
any one help pls.
thx in advance

[cpp]
#include <iostream>
#include <memory.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
const int MAX_PT = 2000;
typedef struct {
double x,y;
} point_t;
point_t pt[MAX_PT];
int st[MAX_PT];
int top,num,mini;
double minx,miny;
inline double multi (point_t p0,point_t p1,point_t p2) {
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
inline double dist (point_t p1,point_t p2) {
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
inline int cmp(const void *a,const void *b) {
point_t *t1,*t2;
t1 = (point_t*)a;
t2 = (point_t*)b;
double t = multi(pt[0],*t1,*t2);
if (t>0) {
return -1;
} else if (abs(t)<1e-8) {
double d = dist(pt[0],*t1)-dist(pt[0],*t2);
if (d>0)
return -1;
else if (abs(d)<1e-8)
return 0;
else
return 1;
} else {
return 1;
}
}
void sort () {
point_t tmp;
memcpy(&tmp,&pt[0],sizeof(point_t));
memcpy(&pt[0],&pt[mini],sizeof(point_t));
memcpy(&pt[mini],&tmp,sizeof(point_t));
qsort(&pt[1],num-1,sizeof(point_t),cmp);
}
void solve () {
int i;
double len;
st[0] = 0;
st[1] = 1;
st[2] = 2;
top = 2;
for (i=3;i<num;i++) {
while (multi(pt[st[top-1]],pt[st[top]],pt)<0) {
top--;
assert(top);
}
top++;
st[top] = i;
}
len = dist(pt[st[0]],pt[st[top]]);
cout.setf(ios::fixed);
cout.precision(1);
cout<<"("<<pt[st[0]].x<<","<<pt[st[0]].y<<")";
for (i=top;i>0;i--) {
cout<<"-("<<pt[st].x<<","<<pt[st].y<<")";
len += dist(pt[st],pt[st[i-1]]);
}
cout<<"-("<<pt[st[0]].x<<","<<pt[st[0]].y<<")"<<endl;
cout.precision(2);
cout<<"Perimeter length = "<<len<<endl<<endl;
}
int main () {
int cas = 1;
cin>>num;
while (num) {
mini = 0; minx = miny = 50000;
for (int i=0;i<num;i++) {
cin>>pt.x>>pt.y;
if (pt.y<miny) {
mini = i;
miny = pt.y;
minx = pt.x;
} else if (fabs(pt.y-miny)<1e-6 && pt[i].x<minx) {
mini = i;
minx = pt[i].x;
}
}
cout<<"Region #"<<(cas++)<<":"<<endl;
sort();
solve();
cin>>num;
}
return 0;
}
[/cpp]

[Yarin]

On the input

12
1 1
1 4
1 3
1 2
1 5
2 5
3 5
4 5
5 5
2 2
3 3
4 4
0

your program outputs a list of 10 vertices, but it should contain all vertices, for instance:

Region #1:
(1.0,1.0)-(1.0,2.0)-(1.0,3.0)-(1.0,4.0)-(1.0,5.0)-(2.0,5.0)-(3.0,5.0)-(4.0,5.0)-(5.0,5.0)-(4.0,4.0)-(3.0,3.0)-(2.0,2.0)-(1.0,1.0)
Perimeter length = 13.66