681 - Convex Hull Finding

[wyvmak]

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]

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]

Somebody wrote the hint that n can be much larger than 512. Maybe that's it?

[jpfarias]

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

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

This was the only change in my code...


Thanx!!!

Jo

[davor]

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

Hey if it's greater than 512, how many would it be?

'Cause I'm getting WA...

[jpfarias]

I've used 1500 in my AC solution.

JP!

[Observer]

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.

[jpfarias]

If the judge output is wrong answer, then you did not get runtime error!

JP!

[Observer]

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.

[Observer]

Fixed the RTE flaw. Now getting WA in 0.447 sec...

[Observer]

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.

[miko'mized]

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?

[..]

My accepted program output the same answer.

[miko'mized]

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