Cod sursa(job #1174250)

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

var ox,oy: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 := oy[(i+j)div 2].y;
  repeat
    while oy[i].y < x do inc(i);
    while oy[j].y > x do dec(j);
    if i <= j then
    begin
      y := oy[i]; oy[i] := oy[j]; oy[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 := sqr(b.x-a.x) + sqr(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;
    for i := 1 to n do
      if (oy[i].x >= bg) and (oy[i].x <= en) then
      begin
        inc(cont);
        v[cont] := oy[i];
      end;

    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);
    oy[i].x := ox[i].x;
    oy[i].y := ox[i].y;
  end;

  QSortX(1,n);
  QSortY(1,n);


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

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