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

官方数据全对了,可在poj还是wa 郁闷~~~~~~~~~~~~~~ 丑丑地贴一下代码

Posted by linmaya at 2011-05-30 19:57:02 on Problem 1113
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:
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