plane
2013-08-12 15:40:03
先求第1个点与其余n-1个点的距离;
再求第2个点与其余n-2个点的距离;
再求第3个点与其余n-3个点的距离;
…………………………………………
再求第n-1个点与其余1个点的距离;
然后找出最小值。
如此的算法复杂度为O(n^2),显然不能满足本题的需要。很遗憾……洛谷神机这回不可以咯……
考虑以下分治算法:
设平面上的点都在点集S中,为了将S线性分割为大小大致相等的2个子集S1和S2,我们选取一垂直线l(方程:x=m)来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}。从而使S1和S2分别位于直线l的左侧和右侧,且S=S1∪S2 。由于m是S中各点x坐标值的中位数,因此S1和S2中的点数大致相等。 递归地在S1和S2上解最接近点对问题,我们分别得到S1和S2中的最小距离δ1和δ2。现设δ=min (δ1,δ2)。
若S的最接近点对(p,q)之间的距离d(p,q)<δ则p和q必分属于S1和S2。不妨设p∈S1,q∈S2。那么p和q距直线l的距离均小于δ。因此,我们若用P1和P2分别表示直线l的左边和右边的宽为δ的2个垂直长条,则p∈S1,q∈S2
此时,P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。在最坏情况下有n^2/4对这样的候选者。但是P1和P2中的点具有以下的稀疏性质,它使我们不必检查所有这n2/4对候选者。考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者,则必有d(p,q)<δ。满足这个条件的P2中的点有多少个呢?容易看出这样的点一定落在一个δ×2δ的矩形R中,
由δ的意义可知P2中任何2个S中的点的距离都不小于δ。由此可以推出矩形R中最多只有6个S中的点。事实上,我们可以将矩形R的长为2δ的边3等分,将它的长为δ的边2等分,由此导出6个(δ/2)×(2δ/3)的矩形。
因此d(u,v)≤5δ/6<δ 。这与δ的意义相矛盾。也就是说矩形R中最多只有6个S中的点。由于这种稀疏性质,对于P1中任一点p,P2中最多只有6个点与它构成最接近点对的候选者。因此,在分治法的合并步骤中,我们最多只需要检查6×n/2=3n对候选者,而不是n^2/4对候选者。
我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点,但是我们并不确切地知道要检查哪6个点。为了解决这个问题,我们可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中,所以它们在直线l上的投影点距p在l上投影点的距离小于δ。由上面的分析可知,这种投影点最多只有6个。因此,若将P1和P2中所有S的点按其y坐标排好序,则对P1中所有点p,对排好序的点列作一次扫描,就可以找出所有最接近点对的候选者,对P1中每一点最多只要检查P2中排好序的相继6个点。
至此,我们用分治法求出平面最接近点对。
type rec=record
x,y:int64;
end;
var a:array [0..200001] of rec;
tt,ttt,tttt:array [0..200001] of rec;
n,l,m,min:int64;
i,j,k:longint;
procedure sort(l,r:longint);
var i,j:longint;
x,y:rec;
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;
procedure sortt(l,r:longint);
var i,j:longint;
x,y:rec;
begin
i:=l;
j:=r;
x:=tttt[(l+r) div 2];
repeat
while (tttt[i].y<x.y) do inc(i);
while (x.y<tttt[j].y) do dec(j);
if not(i>j)
then
begin
y:=tttt[i];
tttt[i]:=tttt[j];
tttt[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then sortt(l,j);
if i<r then sortt(i,r);
end;
function dis(a,b:rec):int64;
begin
exit(sqr(a.x-b.x)+sqr(a.y-b.y));
end;
function minn(a,b:int64):int64;
begin if a<b then exit(a) else exit(b); end;
function work(le,ri:longint):int64;
var tl,tr,t1,t2,min:int64;
i,j,k,lenr,lenl,p1,p2:longint;
begin
if ri-le=1 then exit(dis(a[ri],a[le]));
if ri-le=2 then exit(minn(minn(dis(a[ri],a[le]),dis(a[ri-1],a[le])),dis(a[le+1],a[ri])));
tl:=work(le,(le+ri) div 2);
tr:=work(((le+ri) div 2)+1,ri);
min:=minn(tl,tr);
t1:=(le+ri) div 2;
t2:=t1+1;
while (t1>=le) and (sqr(a[t1].x-a[(le+ri) div 2].x)<=min) do dec(t1);
inc(t1);
while (t2<=ri) and (sqr(a[t2].x-a[(le+ri) div 2].x)<=min) do inc(t2);
dec(t2);
if (t2=(le+ri) div 2) or (t1=((le+ri) div 2)+1) then exit(min);
for k:=t1 to t2 do tttt[k]:=a[k];
sortt(t1,t2);
for k:=t1 to t2-1 do
begin
for j:=k+1 to minn(k+8,t2) do
begin
min:=minn(min,dis(tttt[k],tttt[j]));
end;
end;
exit(min);
end;
begin
readln(n);
for i:=1 to n do readln(a[i].x,a[i].y);
sort(1,n);
writeln(sqrt(work(1,n)):0:4);
end.