Cod sursa(job #1174282)

Utilizator testtVasilica Ionica testt Data 22 aprilie 2014 14:39:11
Problema Cele mai apropiate puncte din plan Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 2.4 kb
type point=record
       x,y:longint;
     end;

var ox:array[0..100005]of point;
    n,i:longint;
    bufin:array[1..65000]of byte;
    v:array[0..100005]of point;
    bg,en:real;

procedure QSortX(l,h:longint);
var i,j,x:longint;
    y:point;
begin
  i := l; j := h; x := ox[(i+j)div 2].x;
  repeat
    while ox[i].x < x do inc(i);
    while ox[j].x > x do dec(j);
    if i <= j then
    begin
      y := ox[i]; ox[i] := ox[j]; ox[j] := y;
      inc(i); dec(j);
    end;
  until i > j;
  if l < j then QSortX(l,j);
  if i < h then QSortX(i,h);
end;

procedure QSortY(l,h:longint);
var i,j,x:longint;
    y:point;
begin
  i := l; j := h; x := v[(i+j)div 2].y;
  repeat
    while v[i].y < x do inc(i);
    while v[j].y > x do dec(j);
    if i <= j then
    begin
      y := v[i]; v[i] := v[j]; v[j] := y;
      inc(i); dec(j);
    end;
  until i > j;
  if l < j then QSortY(l,j);
  if i < h then QSortY(i,h);
end;

function dist(a,b:point):real;
begin
  dist := (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y);
  dist := sqrt(dist);
end;

function Divide(l,h:longint):real;
var m,i,j,cont,hh:longint;
    min,t,v1,v2:real;
begin
  if h-l+1 <= 3 then
  begin
    min := dist(ox[l],ox[l+1]);

    for i := l to h-1 do
      for j := i+1 to h do
      begin
        t := dist(ox[i],ox[j]);
        if t < min then min := t;
      end;

    Divide := min;
  end
  else
  begin
    m := (l+h) div 2;
    v1 := Divide(l,m); v2 := Divide(m+1,h);
    min := v1; if min > v2 then min := v2;

    bg := ox[m].x-min; en := ox[m].x+min;

    cont := 0;
    i := m;
    while ox[i].x - min <= ox[m].x do
    begin
      inc(cont);
      v[cont] := ox[i];
      inc(i);
    end;
    i := m-1;
    while ox[m].x +min > ox[m].x do
    begin
      inc(cont);
      v[cont] := ox[i];
      dec(i);
    end;

    QSortY(1,cont);

    for i := 1 to cont-1 do
    begin
      hh := i+7; if hh > cont then hh := cont;
      for j := i+1 to hh do
      begin
        t := dist(v[i],v[j]);
        if t < min then min := t;
      end;
    end;

    Divide := min;

  end;

end;

begin
  assign(input,'cmap.in'); reset(input);
  assign(output,'cmap.out'); rewrite(output);
  settextbuf(input,bufin);

  readln(n);
  for i := 1 to n do
  begin
    readln(ox[i].x,ox[i].y);
  end;

  QSortX(1,n);


  writeln(Divide(1,n):0:6);

  close(input);
  close(output);
end.