## 681 - Convex Hull Finding

Moderator: Board moderators

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
my approach is:

pick point with min y, if more than one, pick min x with y, say P
sort the angles of all points to P
while(pts>=3 && first_three_points_collinear) remove_second_point
while(pts>=3 && last_three_points_collinear) remove_second_last_point for(i=3; i<pts; ++i) {
while(i && V,V[i-1],V[0] collinear) {
remove V[i-1];
--pts;
--i;
}
while(i>=3 && half_angle(V[0],V[i-2],V[i-1],V) ) {
remove V[i-1];
--pts;
--i;
}
}

half_angle returns true if angle V[i-1] is larger than 180 degrees, i need V[0] because it helps to know which angle on V[i-1] (there're two) to be considered, ie. which side is in the polygon or outside

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### 681 again (the previous one was getting too big)

Hi, again!!!

I've implemented Jarvin's march to solve this problem and I'm still getting WA!!! (I had implemented Graham Scan also!)

I'm asking to someone who solved this problem (got AC) to send your solution again to the judge to see if the input/output of the judge got messed....
(if you could send me your code too, I'll be glad - just to compare with my one )

Jo

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Somebody wrote the hint that n can be much larger than 512. Maybe that's it?

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

### GOT AC!!!!!!!!!!!!!!!!!!!!

Hey! Finally I've got AC!!!!

Really n is > 512!! Fucking description!!!!!

This was the only change in my code...

Thanx!!!

Jo

davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

### 681 finding convex hull

[pascal]
Can anybody tell me what's wrong whit my solution? WA after Being Judged :program p123(input,output);
var b:array[0..1000] of boolean;
a:array[0..1000,1..2] of integer;
c:array[1..1000,1..2] of integer;
n,i,u,v,j,k,l:integer;

function ccw(k1,k2,k3:integer):boolean;
var p:real;
begin
p:=a[k1,1]*(a[k2,2]-a[k3,2])+a[k2,1]*(a[k3,2]-a[k1,2])+a[k3,1]*(a[k1,2]-a[k2,2]);
if p>0 then ccw:=false else ccw:=true;
end;

begin
for u:=1 to v do begin
a[0,1]:=0; a[0,2]:=30000;
k:=0; j:=0;
for i:=1 to n do begin
if (a[i,2]<a[k,2]) or ((a[i,2]=a[k,2]) and (a[i,1]<=a[k,1])) then k:=i;
end;
while (b[k]=false) do begin
l:=1;
b[k]:=true;
for i:=1 to n do begin
if ((a[i,1]<>a[k,1]) and (a[i,2]<>a[k,2])) and (ccw(k,l,i)=true) then l:=i;
end;
j:=j+1;
c[j,1]:=a[k,1]; c[j,2]:=a[k,2];
k:=l;
end;
j:=j+1;
c[j,1]:=a[k,1]; c[j,2]:=a[k,2];
writeln(j);
for i:=1 to j do writeln(c[i,1],' ',c[i,2]);
if u<v then writeln('-1');
end;
end.

[/pascal]

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hey if it's greater than 512, how many would it be?

'Cause I'm getting WA...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
I've used 1500 in my AC solution.

JP!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Here's my judge result:

1813611 2003/08/20 11:56:04.821 Wrong Answer 0:00.012 64 31459 PASCAL 681 - Convex Hull Finding

So obviously, my program got a runtime error!!
Plz help!! Anyone please provide me with some test data.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
If the judge output is wrong answer, then you did not get runtime error!

JP!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Well, I tried to add the following line to the end of my code:

Code: Select all

``while true do;``
It's strange to say that it didn't give me TLE, but WA!! That means the program is terminated by some sort of errors!!!

P.S. I didn't use any Halt or Exit statements in my program.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Fixed the RTE flaw. Now getting WA in 0.447 sec...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Finally got AC-ed! Yeah!

The error turns out to be a stupid flaw on my sorting part (I implemented Graham Scan)....

Btw, I've considered the max. value of n = 520, and I think it's more than enough.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

miko'mized
New poster
Posts: 8
Joined: Thu Dec 04, 2003 4:56 pm

### 681

for this test :
1
15
0 0
1 0
2 0
3 0
4 0
4 1
4 2
4 3
4 4
3 3
2 2
1 3
0 4
0 3
0 2
0 1

anwser:
1
5
0 0
4 0
4 4
0 4
0 0
is correct?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
My accepted program output the same answer.
My signature: