In my solution, I used sentinel 10001, because according to the statement 0 ≤ x, y ≤ 10000. I had runtime error (for that reason). when I replaced 10001 with some big number, got AC. So, I think in Test 12, There is Point with x coordinate 10001. Edited by author 16.10.2013 15:42 And now WA#13 Baker's dozen! Edited by author 25.04.2006 19:43 I have found the silly mistake It's helped me: 23 0 8 1 2 2 1 2 3 2 4 2 5 2 6 3 1 3 2 3 3 3 4 3 5 3 7 4 1 4 2 4 4 4 6 5 1 5 3 5 5 6 2 6 4 7 3 what's the answer? 2 I have WA 14 many times, because cos between two vectors(use floating operations) some times give wrong result. Solution accepted with EPS for comparation of cosinus = 1e-15. Edited by author 24.10.2010 19:50 В слове "подаваться" На выход должно подвааться единственное целое число -> На выход должно подаваться единственное целое число I got WA#13 and I don't understand what's wrong in my program. I try tests from UNKNOWN_LAMER, and my program passed them. Please give me some interesting tests! 12 0 0 10 0 20 0 0 10 0 20 5 20 12 20 20 10 20 20 10 20 3 3 4 4 Answer: 1 Try this test: 2 1 0 2 0 P.S. Though N>2,this can appear in a little big test. why do you have to be cryptic! 12 0 0 10 0 20 0 0 10 0 20 5 20 12 20 20 10 20 20 10 20 3 3 4 4 Answer: 1 Anyone with the same WA? I think Java is starting to be the problem... Is there a trick? I must forget something, because i tried 3 different implementations for finding the current convex hull of the points, and all three get WA 10... What does you program output on the following test: 3 0 0 1 1 2 2 ? What does you program output on the following test: 3 0 0 1 1 2 2 ? 0 It's ok. Try this: 8 0 0 0 1 0 2 1 0 1 2 2 0 2 1 2 2 It's ok. Try this: 8 0 0 0 1 0 2 1 0 1 2 2 0 2 1 2 2 1 :) Is there a chance, you looked at my code? It's not so long, and I'll put some comments. If you don't want to get involved, I'll understand :) Ok, send it to nick[youknowwhat]inbox[youknowwhatagain]ru, using goryinyich instead of nick message is sent, thank you in advance! Received. But I'll have time to look at it only in saturday-sunday... Your code gets WA on the following test: 33 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 -1 1 -2 2 -3 3 -4 4 -5 5 -6 6 -7 7 -8 8 -9 9 -10 10 -11 11 0 -1 0 -2 0 -3 0 -4 0 -5 0 -6 0 -7 0 -8 0 -9 0 -10 0 -11 By the way, even if you correct the error, it will get TLE: for the test generated by the following Pascal code you program doesn't finish the job in 1 minute: var i, n: integer; begin n := 1333; rewrite (output, 'input.txt'); writeln (3*n); for i := 1 to n do writeln (i , ' ', i); for i := 1 to n do writeln (-i , ' ', i); for i := 1 to n do writeln (0 , ' ', -i); end. AC atlast :) Thanks man, I had 2 big problems, but all fixed with +10 lines code. Thank you for great test! Hey how did you solve the TLE? nevermind.. .acos takes a looot of time My algorithm is to find the convex hull until the numbers of the point on the convex hull is less than 3. Could anyone tell me what's wrong?or give me some useful test case? If outermost fence leaves some point outside, this outer point will not affect further inner fences, and it is always possible to include that point without worsening the situation. Edited by author 20.08.2008 13:17 I tried all tests which are posted here and it gives me correct answer, but I have WA #3!!! Someone help me, please! Can you post some more tests??? Try this test case: 10 10 0 0 10 0 0 10 10 0 5 5 0 10 5 5 10 5 5 7 8 Answer is 1. 1) 12 1 0 0 1 0 2 2 0 2 1 1 2 1 3 3 1 1 1 2 2 2 3 3 2 Answer:2 2) 6 0 0 4 0 2 0 2 4 1 2 3 2 Answer:1 3) 7 0 0 0 100 100 0 100 100 50 50 50 25 50 75 Answer:1 Good luck! I've passed all these tests, but my program give WA at #3. Please help me. Thanks in advaced I'm a newbie, and I don't know why i'm wrong at test #3. Thanks in advanced. const inp=''; out=''; var i,c,count,m,n:longint; x1,y1,p,x,y:array[1..4005] of integer; mark:array[1..4005] of 0..1; f:text; function lower(i,j:integer):boolean; begin { lower:=false; if (y[i]=y[1]) and (y[j]=y[1]) then if x[i]<x[j] then lower:=true else if(x[i]=x[1]) and (x[j]=x[1]) then if y[i]>y[j] then lower:=true else } lower:=(y[i]-y[1])*(x[j]-x[1])<(x[i]-x[1])*(y[j]-y[1]); end; procedure swap(i,j:integer); var t:integer; begin t:=x[i]; x[i]:=x[j]; x[j]:=t; t:=y[i]; y[i]:=y[j]; y[j]:=t; end; {----------------------------------------------------------------------} procedure Qsort(left,right:integer); var l,r,m:integer; begin l:=left; r:=right; m:=(l+r) div 2; while l<r do begin while lower(l,m) do inc(l); while lower(m,r) do dec(r); if (l<=r) then begin swap(l,r); inc(l); dec(r); end; end; if left<r then qsort(left,r); if l<right then qsort(l,right); end; {----------------------------------------------------------------------} procedure input; var f:text; i,j:integer; begin assign(f,inp); reset(f); readln(f,n); readln(f,x[1],y[1]); p[1]:=1; for i:=2 to n do begin readln(f,x[i],y[i]); end; end; {----------------------------------------------------------------------} function CCW(i,j,k:integer):integer; var t,a1,b1,a2,b2:integer; begin a1:=x[j]-x[i]; b1:=y[j]-y[i]; a2:=x[k]-x[j]; b2:=y[k]-y[j]; t:=a1*b2-a2*b1; if t=0 then ccw:=0 else if t>0 then ccw:=1 else ccw:=-1; end; {----------------------------------------------------------------------} procedure find; var t,i,j:integer; begin t:=1; for i:=2 to n do if y[i]<y[t] then t:=i else if y[i]=y[t] then if x[i]>x[t] then t:=i; swap(1,t); Qsort(2,n); j:=2; m:=2;p[1]:=1; p[2]:=2; for i:=3 to n do begin while (ccw(p[m-1],p[m],i)<>1) and (m>1) do dec(M); inc(m); p[m]:=i; end; fillchar(mark,sizeof(mark),0); mark[1]:=1; for i:=1 to m do mark[p[i]]:=1; end; begin input; count:=0; c:=n; repeat; find; c:=0; if (m<3) or (ccw(p[1],p[2],p[m])=0) then break; inc(count); for i:=1 to n do if mark[i]=0 then begin inc(c); x1[c]:=x[i]; y1[c]:=y[i]; end; y:=y1; x:=x1; n:=c; until c<3; assign(f,out); rewrite(f); writeln(f,count); close(f); end. Almost everyone have go WA#13 at least once? What is that test? I can't find any mistakes in my program, but still WA#13 :(( I've got AC but my run time is 0.765s . I saw that some people got AC with little run time so I think there's another solution better than using Graham k times ( k = maximal possible number of fences ). If it's true , please tell me your solution. Thank you very much. My e-mail : hard7771988@yahoo.co.uk To solve this problem efficiently we have to use Chazelle's algorith which is O(n log n). Sometimes it's called "onion peeling algorithm". But I can't find this algorithm in the net. If someone knows , please tell us links to it. TheBeet 1418 C++ Accepted 0.093 206 KB I use Graham k times. My solution is O(n^2) |
|