Pagini recente » Cod sursa (job #3237383) | Cod sursa (job #98091) | Cod sursa (job #3240010) | Cod sursa (job #3209155) | Cod sursa (job #1174255)
type point=record
x,y:longint;
end;
var ox,oy:array[0..100005]of point;
n,i:longint;
bufin:array[1..65000]of byte;
v:array[0..100005]of point;
bg,en:real;
procedure QSortX(l,h:longint);
var i,j,x:longint;
y:point;
begin
i := l; j := h; x := ox[(i+j)div 2].x;
repeat
while ox[i].x < x do inc(i);
while ox[j].x > x do dec(j);
if i <= j then
begin
y := ox[i]; ox[i] := ox[j]; ox[j] := y;
inc(i); dec(j);
end;
until i > j;
if l < j then QSortX(l,j);
if i < h then QSortX(i,h);
end;
procedure QSortY(l,h:longint);
var i,j,x:longint;
y:point;
begin
i := l; j := h; x := oy[(i+j)div 2].y;
repeat
while oy[i].y < x do inc(i);
while oy[j].y > x do dec(j);
if i <= j then
begin
y := oy[i]; oy[i] := oy[j]; oy[j] := y;
inc(i); dec(j);
end;
until i > j;
if l < j then QSortY(l,j);
if i < h then QSortY(i,h);
end;
function dist(a,b:point):real;
begin
dist := 0;
exit;
dist := sqr(b.x-a.x) + sqr(b.y-a.y);
dist := sqrt(dist);
end;
function Divide(l,h:longint):real;
var m,i,j,cont,hh:longint;
min,t,v1,v2:real;
begin
if h-l+1 <= 3 then
begin
min := dist(ox[l],ox[l+1]);
for i := l to h-1 do
for j := i+1 to h do
begin
t := dist(ox[i],ox[j]);
if t < min then min := t;
end;
Divide := min;
end
else
begin
m := (l+h) div 2;
v1 := Divide(l,m); v2 := Divide(m,h);
min := v1; if min > v2 then min := v2;
bg := ox[m].x-min; en := ox[m].x+min;
cont := 0;
for i := 1 to n do
if (oy[i].x >= bg) and (oy[i].x <= en) then
begin
inc(cont);
v[cont] := oy[i];
end;
for i := 1 to cont-1 do
begin
hh := i+7; if hh > cont then hh := cont;
for j := i+1 to hh do
begin
t := dist(v[i],v[j]);
if t < min then min := t;
end;
end;
Divide := min;
end;
end;
begin
assign(input,'cmap.in'); reset(input);
assign(output,'cmap.out'); rewrite(output);
settextbuf(input,bufin);
readln(n);
for i := 1 to n do
begin
readln(ox[i].x,ox[i].y);
oy[i].x := ox[i].x;
oy[i].y := ox[i].y;
end;
QSortX(1,n);
QSortY(1,n);
writeln(Divide(1,n):0:6);
close(input);
close(output);
end.