Cod sursa(job #728162)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 28 martie 2012 15:33:23
Problema Cele mai apropiate puncte din plan Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 2.12 kb

type punct=record
  x,y:int64;
end;
type vector=array[1..100000]of punct;

var i,j:longint;
   n:int64;
v:vector;
min:real;


procedure qsort(var a :vector);

    procedure sort(l,r: longint);
      var
         i,j:longint;
         x,y:punct;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while (a[i].x<x.x)or((a[i].x=x.x)and (a[i].y<x.y)) do
            inc(i);
           while (x.x<a[j].x)or ((x.x=a[j].x)and (x.y<a[j].y)) do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

    begin
       sort(1,n);
    end;


procedure qsort1(var a :vector);

    procedure sort(l,r: longint);
      var
         i,j:longint;
         x,y:punct;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while (a[i].y<x.y)or((a[i].x=y.y)and (a[i].x<x.x)) do
            inc(i);
           while (x.y<a[j].y)or ((x.x=a[j].y)and (x.x<a[j].x)) do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

    begin
       sort(1,n);
    end;


function calc(a,b:punct):real;
var a1,a2:int64;
begin
a1:=abs(a.x-b.x);
a2:=abs(a.y-b.y);
calc:=sqrt(sqr(a1)+sqr(a2));
end;

begin
assign(input,'cmap.in');reset(input);
assign(output,'cmap.out');rewrite(output);
readln(n);
min:=maxlongint;
for i:=1 to n do read(v[i].x,v[i].y);
qsort(v);
for i:=1 to n-1 do
if calc(v[i],v[i+1])<min then min:=calc(v[i],v[i+1]);
qsort1(v);
for i:=1 to n-1 do
if calc(v[i],v[i+1])<min then min:=calc(v[i],v[i+1]);

writeln(min:0:6);
close(output);
end.