Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

蒟蒻求解WA

Posted by Hoblovski at 2014-05-21 14:20:49 on Problem 3348 and last updated at 2014-05-21 14:31:56
此题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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator