Cod sursa(job #426394)

Utilizator sapiensCernov Vladimir sapiens Data 26 martie 2010 20:48:02
Problema Cele mai apropiate puncte din plan Scor 20
Compilator fpc Status done
Runda Arhiva educationala Marime 2.09 kb
Program Cmap;
 type punct = record
                u,v:int64;
              end;
 var f,g:text; p:array[0..100001]of punct;
     i,n,nh:longint;
 procedure swap (x,y:int64);
  var i:punct;
  begin
   i:=p[x]; p[x]:=p[y]; p[y]:=i;
  end;
 function mm (x,y:longint):boolean;
  begin
   if (p[x].u<p[y].u) then exit (false) else
     if (p[x].u>p[y].u) then exit (true) else
       if (p[x].v>p[y].v) then exit (true) else exit (false);
  end;
 procedure sift (x:int64);
  var i,j:longint;
  begin
   i:=x; j:=i;
   while (i=j) do begin
     j:=0;
     if 2*i<=nh then begin
       j:=2*i;
       if (j+1<=nh) then if mm (j+1,j) then j:=j+1;
       if mm (j,i) then begin
         swap (i,j);
         i:=j;
       end;
     end;
   end;
  end;
 procedure percolate (x:int64);
  var i:longint;
  begin
   i:=x;
   while (i<>1) and mm (i,i div 2) do begin
     swap (i div 2,i);
     i:=i div 2;
   end;
  end;
 procedure delete_1;
  begin
   swap (1,nh);
   dec (nh);
   sift (1);
  end;
 function dist (x,y:int64):real;
  begin
   exit (sqrt (sqr (p[x].u-p[y].u)+sqr (p[x].v-p[y].v)));
  end;
 function min (x,y:real):real;
  begin
   if x<y then exit (x) else exit (y);
  end;
 function dmin (x,y:int64):real;
  var z:real; m,li,ls,i,j:longint;
  begin
   if y-x=1 then exit (dist (x,y));
   if y-x=2 then exit (min (min (dist (x,x+1),dist (x,y)),dist (x+1,y)));
   m:=(x+y) div 2;
   z:=min (dmin (x,m),dmin (m+1,y));
   li:=m-1; ls:=m+1;
   while (p[m].u-p[li].u<z) and (li>0) do dec (li);
   while (p[ls].u-p[m].u<z) and (ls<=n) do inc (ls);
   for i:=li+1 to ls-2 do
     for j:=i+1 to i+8 do
       if j<ls then z:=min (z,dist (i,j));
//   for i:=x to y-1 do
//     for j:=i+1 to i+8 do
//       if (i+8<=y) then z:=min (z,dist (i,j));
   exit (z);
  end;
 begin
  assign (f,'cmap.in'); reset (f);
  assign (g,'cmap.out'); rewrite (g);
  readln (f,n);
  nh:=0;
  for i:=1 to n do begin
    inc (nh);
    readln (f,p[nh].u,p[nh].v);
    percolate (nh);
  end;
  for i:=1 to n-1 do delete_1;
  writeln (g,dmin (1,n):1:6);
  close (f); close (g);
 end.