Cod sursa(job #591166)

Utilizator ion_calimanUAIC Ion Caliman ion_caliman Data 22 mai 2011 20:29:41
Problema Cele mai apropiate puncte din plan Scor 30
Compilator fpc Status done
Runda Arhiva educationala Marime 1.99 kb
var     x,y:array[1..100000] of extended;
        n,i:longint;
        d:extended;
        f,g:text;

procedure sw(var a,b:extended);
var     t:extended;
begin
  t:=a; a:=b; b:=t;
end;

procedure qs(left,right:longint);
var     i,j:longint;
        r:extended;
begin
  i:=left;
  j:=right;
  r:=x[(i+j) div 2];
  while i<j do
    begin
      while x[i]<r do inc(i);
      while x[j]>r do dec(j);
      if i<=j then
        begin
          sw(x[i],x[j]);
          sw(y[i],y[j]);
          inc(i);
          dec(j);
        end;
    end;
  if i<right then qs(i,right);
  if j>left then qs(left,j);
end;

procedure qs2(left,right:longint);
var     i,j:longint;
        r:extended;
begin
  i:=left;
  j:=right;
  r:=y[(i+j) div 2];
  while i<j do
    begin
      while y[i]<r do inc(i);
      while y[j]>r do dec(j);
      if i<=j then
        begin
          sw(x[i],x[j]);
          sw(y[i],y[j]);
          inc(i);
          dec(j);
        end;
    end;
  if i<right then qs(i,right);
  if j>left then qs(left,j);
end;

function min(a,b:extended):extended;
begin
  if a<b then min:=a else min:=b;
end;

function dis(left,right:longint):extended;
var     i,j,r:longint;
begin
  if right-left>2 then
    begin
      r:=(left+right) div 2;
      dis:=min(dis(left,r),dis(r+1,right));
      {dis:=min(dis,dis(r-2,r+2))}
    end else
    if right-left=2 then
    begin
      dis:=min(sqrt(sqr(x[left]-x[left+1])+sqr(y[left]-y[left+1])),
                sqrt(sqr(x[left]-x[left+2])+sqr(y[left]-y[left+2])));
      dis:=min(dis,sqrt(sqr(x[left+2]-x[left+1])+sqr(y[left+2]-y[left+1])));
    end else
    if right-left=1 then
    begin
      dis:=sqrt(sqr(x[left]-x[left+1])+sqr(y[left]-y[left+1]));
    end;
end;

begin
  assign(f,'cmap.in');
  assign(g,'cmap.out');
  reset(f);
  rewrite(g);
  readln(f,n);
  for i:=1 to n do
    readln(f,x[i],y[i]);
  qs(1,n);
  d:=dis(1,n);
  qs2(1,n);
  d:=min(d,dis(1,n));
  writeln(g,d:0:6);
  close(g);
end.