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 |
官方数据全对了,可在poj还是wa 郁闷~~~~~~~~~~~~~~ 丑丑地贴一下代码type dian=record x,y:longint; end; var yuan:dian; ce,cei,n,h,t,mini,i,m:longint; dui:array[1..100000] of dian; a:array[1..100000] of dian; pd:boolean; ans:double; function chaji(b,c,a:dian):double; begin b.x:=b.x-a.x; c.x:=c.x-a.x; b.y:=b.y-a.y; c.y:=c.y-a.y; exit((b.x*c.y-b.y*c.x)); end; function dist(a,b:dian):double; begin exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))) end; procedure swap(var a,b:dian); var t:dian; begin t:=a; a:=b; b:=t; end; procedure paixu(l,r:longint); var i,j,mid:longint; t:dian; begin if l>=r then exit; i:=l; j:=r; mid:=random(r-l+1)+l; repeat while (chaji(a[mid],a[i],yuan)>0) or (abs(chaji(a[mid],a[i],yuan))=0) and (dist(a[i],yuan)<dist(a[mid],yuan)) do inc(i); while (chaji(a[j],a[mid],yuan)>0) or (abs(chaji(a[j],a[mid],yuan))=0) and (dist(a[j],yuan)>dist(a[mid],yuan)) do dec(j); swap(a[i],a[j]); if i=mid then mid:=j else if j=mid then mid:=i; until i=j; paixu(l,i-1); paixu(i+1,r); end; procedure paixu2(l,r:longint); var i,j,mid:longint; t:dian; begin if l>=r then exit; i:=l; j:=r; mid:=random(r-l+1)+l; repeat while dist(a[i],yuan)>dist(a[mid],yuan) do inc(i); while (dist(a[j],yuan)<dist(a[mid],yuan)) do dec(j); swap(a[i],a[j]); if i=mid then mid:=j else if j=mid then mid:=i; until i=j; paixu2(l,i-1); paixu2(i+1,r); end; procedure chuli; var i,j:longint; p:dian; begin for i:=n downto 2 do begin if chaji(a[i],a[i-1],yuan)<>0 then begin paixu2(i,n); break; end else if i=3 then break; end; end; procedure granham; var i,j:longint; jiaguo,shang:boolean; begin h:=0; t:=1; dui[1]:=yuan; for i:=2 to n do begin while (t-h>=2) and (chaji(a[i],dui[t],dui[t-1])<=0) do dec(t); inc(t); dui[t]:=a[i]; end; end; begin {assign(input,'wall.in') ;assign(output,'wall.out'); rewrite(output); reset(input); } begin ans:=0; readln(n,m); pd:=false; for i:=1 to n do readln(a[i].x,a[i].y); mini:=1; for i:=2 to n do begin if (a[i].x<a[mini].x) or (abs(a[i].x-a[mini].x)=0) and (a[i].y<a[mini].y) then mini:=i; end; swap(a[1],a[mini]); yuan:=a[1]; paixu(2,n); // chuli; granham; ans:=0; for i:=h+2 to t do ans:=ans+dist(dui[i],dui[i-1]); ans:=ans+dist(dui[h+1],dui[t]) ; if n>1 then writeln(ans+2*3.1415926535897*m:0:0) end; close(output); close(input); end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator