记录编号	40502	评测结果	PPPPPPPPPP
题目名称	[河南省队2012] 信使问题b	最终得分	50
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	0.410 s
提交时间	2012-07-17 22:02:26	内存使用	3.22 MiB

const
  oo=1000000000000;

type
  jp=record
    x,y:double;
  end;

var
  n,i:longint;
  a,b:array[0..100000]of jp;

function min(x,y:double):double;
begin
  if x<y then min:=x
  else min:=y;
end;

procedure sort(l,r:longint);
var
  i,j:longint;
  xx,yy:double;
begin
  i:=l;
  j:=r;
  xx:=a[(l+r) div 2].x;
  repeat
    while a[i].x<xx do inc(i);
    while xx<a[j].x do dec(j);
    if i<=j then
    begin
      yy:=a[i].x;
      a[i].x:=a[j].x;
      a[j].x:=yy;

      yy:=a[i].y;
      a[i].y:=a[j].y;
      a[j].y:=yy;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;

procedure sortt(l,r:longint);
var
  i,j:longint;
  xx,yy:double;
begin
  i:=l;
  j:=r;
  xx:=b[(l+r) div 2].y;
  repeat
    while b[i].y<xx do inc(i);
    while xx<b[j].y do dec(j);
    if i<=j then
    begin
      yy:=b[i].x;
      b[i].x:=b[j].x;
      b[j].x:=yy;

      yy:=b[i].y;
      b[i].y:=b[j].y;
      b[j].y:=yy;
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then sortt(i,r);
  if l<j then sortt(l,j);
end;

function dis(i,j:longint):double;
var
  x1,y1,x2,y2:double;
begin
  x1:=a[i].x;
  y1:=a[i].y;
  x2:=a[j].x;
  y2:=a[j].y;
  dis:=sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
end;

function diss(i,j:longint):double;
var
  x1,y1,x2,y2:double;
begin
  x1:=b[i].x;
  y1:=b[i].y;
  x2:=b[j].x;
  y2:=b[j].y;
  diss:=sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
end;

function closest(l,r:longint):double;
var
  mid,i,j,t:longint;
  d1,d2,d:double;
begin
  if l=r then exit(oo);
  if l+1=r then exit(dis(l,r));
  mid:=(l+r) div 2;
  d1:=closest(l,mid);
  d2:=closest(mid+1,r);
  d:=min(d1,d2);
  t:=0;
  for i:=l to r do
  if ((a[mid].x-a[i].x<=d)and(i<=mid))
  or((a[i].x-a[mid].x<=d)and(i>mid))then
  begin
    inc(t);
    b[t].x:=a[i].x;
    b[t].y:=a[i].y;
  end;
  sortt(1,t);
  for i:=1 to t do
   for j:=i+1 to t do
   begin
     if b[j].y-b[i].y>d then break;
     d:=min(d,diss(i,j));
   end;
  closest:=d;
end;

begin
  assign(input,'postmanb.in'); reset(input);
  assign(output,'postmanb.out'); rewrite(output);
  readln(n);
  for i:=1 to n do readln(a[i].x,a[i].y);
  sort(1,n);
  writeln(0.0000);
  writeln(closest(1,n):0:4);
  close(input);
  close(output);
end.