Moderator: Board moderators

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

Wedson
New poster
Posts: 3
Joined: Sun Nov 25, 2001 2:00 am
Location: Brazil
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

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

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
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:
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
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
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
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
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

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

[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:
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