Pagini recente » Cod sursa (job #2642513) | Borderou de evaluare (job #3171567) | Cod sursa (job #1227017) | Cod sursa (job #659180) | Cod sursa (job #425476)
Cod sursa(job #425476)
Program Cmap;
type punct = record
u,v:longint;
end;
var f,g:text; p:array[0..100000]of punct;
i,n,nh:longint;
procedure swap (x,y:longint);
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:longint);
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:longint);
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 afisare;
var i:longint;
begin
for i:=1 to n do writeln (p[i].u:4,p[i].v:4);
writeln;
end;
procedure delete_1;
begin
swap (1,nh);
dec (nh);
sift (1);
end;
function dist (x,y:longint):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:longint):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; ls:=m;
while (dist (li,m)<z) do dec (li);
while (dist (m,ls)<z) do inc (ls);
inc (li); dec (ls);
for i:=li to ls-1 do
for j:=li+1 to li+8 do
if j<=ls 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));
close (f); close (g);
end.