681 - Convex Hull Finding

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

Moderator: Board moderators

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

Post by wyvmak » Tue Jun 18, 2002 3:59 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)

Post by jpfarias » Mon Jun 24, 2002 11:21 pm

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 ;-))
Thanx in advance!!


Jo

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Mon Jun 24, 2002 11:27 pm

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

Post by jpfarias » Tue Jun 25, 2002 3:19 pm

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

Post by davor » Sat Jun 28, 2003 11:19 pm

[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
readln(v);
for u:=1 to v do begin
readln(n);
a[0,1]:=0; a[0,2]:=30000;
k:=0; j:=0;
for i:=1 to n do begin
readln(a[i,1],a[i,2]); b:=false;
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;
if u<v then readln(i);
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

Post by Observer » Mon Aug 18, 2003 8:16 am

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:

Post by jpfarias » Mon Aug 18, 2003 1:29 pm

I've used 1500 in my AC solution. :-)

JP!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Aug 20, 2003 2:02 pm

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

Post by jpfarias » Wed Aug 20, 2003 4:23 pm

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

Post by Observer » Fri Aug 22, 2003 5:34 am

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

Post by Observer » Fri Aug 22, 2003 6:17 am

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

Post by Observer » Thu Nov 13, 2003 5:47 pm

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

Post by miko'mized » Thu Dec 04, 2003 4:59 pm

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

Post by .. » Thu Dec 04, 2003 5:56 pm

My accepted program output the same answer.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

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

Post by miko'mized » Thu Dec 04, 2003 7:07 pm

Thx, then everything in my program seems to be alright. But it isn't :|

Post Reply

Return to “Volume 6 (600-699)”