Cod sursa(job #502112)

Utilizator zseeZabolai Zsolt zsee Data 17 noiembrie 2010 19:27:27
Problema Cele mai apropiate puncte din plan Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 2.23 kb
program pontokasikban;

type pont=record x,y:int64; end;

var v: array[0..100000] of pont;
 rbuf: array[1..32000] of byte;
 be,ki:text;
 n,i,j,b,e:longint;
 mind,dt:double;

function d(a,b:pont):double;inline;
begin
 d:= sqrt( sqr(a.x-b.x) + sqr(a.y-b.y) );
end;

function nagyobb(a,b:pont):boolean;inline;
begin
 if a.x = b.x then
    nagyobb := a.y > b.y
   else
    nagyobb := a.x > b.x;
end;

procedure feloszt(bal,jobb:longint; var m:longint);
var
  i,j:longint;
  elvalaszto,seged:pont;

begin
 elvalaszto:= v[(bal+jobb)div 2];
 i:=bal;
 j:=jobb;
 repeat
   while nagyobb(v[j],elvalaszto) do
      dec(j);
   while nagyobb(elvalaszto,v[i]) do
      inc(i);
   if i<j then
     begin
      seged:=v[i];
      v[i]:=v[j];
      v[j]:=seged;
     end;
 until i>=j;
 m:=j;
end;

procedure QuickSort(bal,jobb:longint);
var
  m:longint;
begin
  if bal<jobb then
   begin
     feloszt(bal,jobb,m);
     QuickSort(bal,m);
     QuickSort(m+1,jobb);
   end;
end;

function findx( x:int64 ):longint;inline;
var b,e:longint;
begin
 b:=0;
 e:=n-1;
 while b<e do
  if v[ (b+e)shr 1 ].x >= x then e := ( (b+e)shr 1 )-1
                            else b := ( (b+e)shr 1 )+1;
 findx := b;
end;

function findy( y:int64; b,e:longint):longint;inline;
begin
 while b<e do
  if v[ (b+e)shr 1 ].y >= y then e := ( (b+e)shr 1 )-1
                            else b := ( (b+e)shr 1 )+1;
 findy := b;
end;

function max(a,b:longint):longint;inline;
begin
 if a>b then max:=a else max:=b;
end;


begin
 assign(be,'cmap.in');
 assign(ki,'cmap.out');
 settextbuf(be,rbuf);
 reset(be);
 rewrite(ki);
 readln(be,n);
 for i:=0 to n-1 do
   read(be,v[i].x,v[i].y);
 close(be);
 quicksort(0,n-1);
 mind := 0;
 for i:=1 to n-1 do
  begin
   dt := d( v[0], v[i] );
   if (dt < mind)or(mind=0) then mind := dt;
  end;

 for i:=2 to n-1 do
  begin
   b := findx(v[i].x - round(mind) - 1);
   e := findx(v[i].x + round(mind) + 1);
   b := findy(v[i].y - round(mind) - 1 , b , e);
   e := findy( v[i].y + round(mind) + 1, b, e);
   for j:=b to e do
     begin
      dt := d(v[i],v[j]);
      if (dt<mind)and(i<>j) then
        mind := dt;
     end;
  end;
 writeln(ki,mind:1:9);
 close(ki);
end.