Cod sursa(job #502106)

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

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

var v: array[1..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 sort;
var inc,i,j:longint;
    tmp:pont;
begin
 inc:=trunc(n / 2.71828 );
 while inc >= 1 do
   begin
    for i:=inc+1 to n do
      begin
       tmp:=v[i];
       j:=i;
       while (j > inc)and( nagyobb(v[j-inc],tmp) ) do
          begin
           v[j]:=v[j-inc];
           j:=j-inc;
          end;
       v[j]:=tmp;
      end;
    if inc < 11 then
       if inc=1 then
         inc:=0
        else inc:=1
     else inc:=trunc(inc / 2.71828);
   end;
end;

function findx( x:int64 ):longint;inline;
var b,e:longint;
begin
 b:=1;
 e:=n;
 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:=1 to n do
   read(be,v[i].x,v[i].y);
 close(be);
 sort;
 mind := 0;
 for i:=2 to n do
  begin
   dt := d( v[1], v[i] );
   if (dt < mind)or(mind=0) then mind := dt;
  end;

 for i:=2 to n 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.