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