Pagini recente » Cod sursa (job #1222238) | Cod sursa (job #699448) | Cod sursa (job #951651) | Cod sursa (job #1269878) | Cod sursa (job #426394)
Cod sursa(job #426394)
Program Cmap;
type punct = record
u,v:int64;
end;
var f,g:text; p:array[0..100001]of punct;
i,n,nh:longint;
procedure swap (x,y:int64);
var i:punct;
begin
i:=p[x]; p[x]:=p[y]; p[y]:=i;
end;
function mm (x,y:longint):boolean;
begin
if (p[x].u<p[y].u) then exit (false) else
if (p[x].u>p[y].u) then exit (true) else
if (p[x].v>p[y].v) then exit (true) else exit (false);
end;
procedure sift (x:int64);
var i,j:longint;
begin
i:=x; j:=i;
while (i=j) do begin
j:=0;
if 2*i<=nh then begin
j:=2*i;
if (j+1<=nh) then if mm (j+1,j) then j:=j+1;
if mm (j,i) then begin
swap (i,j);
i:=j;
end;
end;
end;
end;
procedure percolate (x:int64);
var i:longint;
begin
i:=x;
while (i<>1) and mm (i,i div 2) do begin
swap (i div 2,i);
i:=i div 2;
end;
end;
procedure delete_1;
begin
swap (1,nh);
dec (nh);
sift (1);
end;
function dist (x,y:int64):real;
begin
exit (sqrt (sqr (p[x].u-p[y].u)+sqr (p[x].v-p[y].v)));
end;
function min (x,y:real):real;
begin
if x<y then exit (x) else exit (y);
end;
function dmin (x,y:int64):real;
var z:real; m,li,ls,i,j:longint;
begin
if y-x=1 then exit (dist (x,y));
if y-x=2 then exit (min (min (dist (x,x+1),dist (x,y)),dist (x+1,y)));
m:=(x+y) div 2;
z:=min (dmin (x,m),dmin (m+1,y));
li:=m-1; ls:=m+1;
while (p[m].u-p[li].u<z) and (li>0) do dec (li);
while (p[ls].u-p[m].u<z) and (ls<=n) do inc (ls);
for i:=li+1 to ls-2 do
for j:=i+1 to i+8 do
if j<ls then z:=min (z,dist (i,j));
// for i:=x to y-1 do
// for j:=i+1 to i+8 do
// if (i+8<=y) then z:=min (z,dist (i,j));
exit (z);
end;
begin
assign (f,'cmap.in'); reset (f);
assign (g,'cmap.out'); rewrite (g);
readln (f,n);
nh:=0;
for i:=1 to n do begin
inc (nh);
readln (f,p[nh].u,p[nh].v);
percolate (nh);
end;
for i:=1 to n-1 do delete_1;
writeln (g,dmin (1,n):1:6);
close (f); close (g);
end.