nearest.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

const maxn = 60001;
      maxs = 6;

type Node  = record
                 pos,x,y:longint;
             end;

     TPoint = array[1..maxn] of Node;

var  Point:TPoint;
     X:array[1..maxn] of longint;
     n:longint;
     tmp:Node;

procedure setIO;
begin
  assign(input,'Nearest.in');
  reset(input);
  assign(output,'Nearest.out');
  rewrite(output);
end;

procedure Qsortx(l,r:longint);
var  i,j,mid:longint;
begin
   i:=l; j:=r;
   mid:=Point[l+random(r-l+1)].x;
   repeat
     while Point[i].x<mid do inc(i);
     while mid<Point[j].x do dec(j);
     if not (i>j) then
       begin
          tmp:=Point[i];  Point[i]:=Point[j];  Point[j]:=tmp;
          inc(i); dec(j);
       end;
   until i>j;
   if l<j then Qsortx(l,j);
   if i<r then Qsortx(i,r);
end;

procedure Qsorty(l,r:longint);
var  i,j,mid:longint;
begin
   i:=l; j:=r;
   mid:=Point[l+random(r-l+1)].y;
   repeat
     while Point[i].y<mid do inc(i);
     while mid<Point[j].y do dec(j);
     if not (i>j) then
       begin
          tmp:=Point[i];  Point[i]:=Point[j];  Point[j]:=tmp;
          inc(i); dec(j);
       end;
   until i>j;
   if l<j then Qsorty(l,j);
   if i<r then Qsorty(i,r);
end;

procedure Init;
var i:longint;
begin
  read(n);
  for i:=1 to n do
      read(Point[i].x,Point[i].y);
  randomize;
  Qsortx(1,n);
  for i:=1 to n do
     begin
        Point[i].pos:=i;
        X[i]:=Point[i].x;
     end;
  Qsorty(1,n);
end;

function min(a,b:real):real;
begin
   if a<b then exit(a)
          else exit(b);
end;

function Distance(i,j:node):real;
begin
   exit(sqrt(sqr(i.x-j.x)+sqr(i.y-j.y)));
end;

function Nearest(l,r:longint; var Point:TPoint):real;
var Topl,Topr,mid,i,j,k,q:longint;
    Tl,Tr:^TPoint;
    m:real;
begin
     if l = r  then exit( maxlongint );
     if (l+1) = r then exit( Distance(Point[1],Point[2]));
     mid:=(l+r) div 2;
     Getmem(Tl,sizeof(Node)*(mid-l+2));
     Getmem(Tr,sizeof(Node)*(r-mid+1));
     Topl:=0; Topr:=0;
     for i:=1 to r-l+1 do
        if Point[i].pos<=mid then
             begin
                  inc(Topl);
                  Tl^[Topl]:=Point[i];
             end
        else begin
                  inc(Topr);
                  Tr^[Topr]:=Point[i];
             end;
     m:=min(Nearest(l,mid,Tl^),Nearest(mid+1,r,Tr^));
     Topl:=0; Topr:=0;
     for i:=1 to r-l+1 do
        if (Point[i].pos<=mid) and (Point[i].x>=(X[mid]-m)) then
             begin
                  inc(Topl);
                  Tl^[Topl]:=Point[i];
             end
        else if (Point[i].pos>mid) and (Point[i].x<=(X[mid]+m)) then
             begin
                  inc(Topr);
                  Tr^[Topr]:=Point[i];
             end;
     j:=1;
     for i:=1 to Topl do
        begin
           while (Tr^[j].y<(Tl^[i].y-m)) and (j<=Topr) do inc(j);
           if j>Topr then break;
           k:=j;
           while (k<=Topr) and ((k-j)<maxs) do
              begin
                 m:=min(m,Distance(Tl^[i],Tr^[k]));
                 inc(k);
              end;
        end;
     Freemem(Tl,sizeof(Node)*(mid-l+2));
     Freemem(Tr,sizeof(Node)*(r-mid+1));
     exit(m);
end;

procedure Print;
begin
  writeln(Nearest(1,n,Point):0:4);
  close(output);
end;

begin
  setIO;
  Init;
  Print;
end.