Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
蒟蒻求解WA此题CCC官方数据AC,对拍几百万组AC,但是POJ上面WA. 虽然我用的是FP 2.6.4,但是我也用FP 2.2.0测了发现没有问题啊 缩行严重还真是对不起了呢 program poj3348; type point=record x,y:longint; end; const maxn=10017; var p:array[0..maxn] of point; s,ch,q:array[0..maxn] of longint; n,m,top,rer:longint; origin:point; function sgn(r:longint):longint; begin if (r<0) then exit(-1); if (r>0) then exit(1); exit(0); end; function crs(a,b,c:point):longint; begin exit( (c.x-a.x)*(c.y-b.y)-(c.x-b.x)*(c.y-a.y) ); end; procedure qsort(l,r:longint); var i,j,k,o:longint; begin i:=l; j:=r; k:=q[l+random(r-l+1)]; repeat while (p[q[i]].y<p[k].y)or((p[q[i]].y=p[k].y)and(p[q[i]].x<p[k].x)) do inc(i); while (p[q[j]].y>p[k].y)or((p[q[j]].y=p[k].y)and(p[q[j]].x>p[k].x)) do dec(j); if i<=j then begin o:=q[i]; q[i]:=q[j]; q[j]:=o; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if j>l then qsort(l,j); end; procedure init; var i,j:longint; begin readln(n); for i:=1 to n do begin readln(p[i].x,p[i].y); q[i]:=i; end; qsort(1,n); origin.x:=0; origin.y:=0; end; procedure graham_scan; var i:longint; begin top:=1; s[top]:=q[1]; for i:=2 to n do begin while (top>1)and(sgn(crs(p[s[top-1]],p[s[top]],p[q[i]]))<=0) do dec(top); inc(top); s[top]:=q[i]; end; for i:=1 to top do ch[i]:=s[i]; rer:=top; top:=1; s[top]:=q[n]; for i:=n-1 downto 1 do begin while (top>1)and(sgn(crs(p[s[top-1]],p[s[top]],p[q[i]]))<=0) do dec(top); inc(top); s[top]:=q[i]; end; for i:=1 to top-1 do ch[i+rer]:=s[i+1]; inc(rer,top-1); end; function area:longint; var i:longint; begin area:=0; for i:=1 to rer-1 do inc(area,(crs(origin,p[ch[i]],p[ch[i+1]]))); end; function ans:longint; begin exit( (abs(area)>>1) div 50 ); end; begin init; graham_scan; writeln(ans); end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator