218 - Moth Eradication

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by simon81 » Tue Dec 11, 2001 10:06 am

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
New poster
Posts: 3
Joined: Thu Oct 18, 2001 2:00 am
Location: Rio de Janeiro, Brasil
Contact:

Post by Casimiro » Tue Dec 11, 2001 8:37 pm

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Dec 27, 2001 11:35 pm

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
New poster
Posts: 6
Joined: Tue Dec 11, 2001 2:00 am
Location: singapore

Post by simon81 » Fri Dec 28, 2001 12:48 pm

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

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

Post by Wedson » Sat Dec 29, 2001 4:40 am

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

218 (Moth Eradication) WA

Post by Revenger » Sat Jun 15, 2002 10:00 am

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
New poster
Posts: 7
Joined: Sat May 25, 2002 8:15 am

a test case

Post by hlchan » Wed Jun 19, 2002 12:24 pm

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

Post by Revenger » Wed Jun 19, 2002 2:20 pm

My program write the same but it still get WA :(

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Wed Jul 24, 2002 7:34 pm

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

Post by wyvmak » Thu Jul 25, 2002 2:30 am

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Jul 25, 2002 9:50 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

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

Post by yiweya » Thu Aug 08, 2002 6:09 am

Can the upper answer be accepted by the judge?

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

Post by Robbie » Thu Aug 08, 2002 10:11 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

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

218 - Moth Eradication

Post by obayashi » Sat Aug 24, 2002 8:51 am

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]
Time makes a fool of memory
And yet my memories still shine

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sat Sep 14, 2002 5:14 pm

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

Post Reply

Return to “Volume 2 (200-299)”