平面上的二维点对问题

xuanyi 2018-03-31 原文

题目描述

给出二维平面上的 \(n\) 个点，求出其中最近的一对点间的距离（欧几里德距离 \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)）。
\(n\le 10^5\)

算法1（暴力）

穷举两个点，计算它们之间的距离，时间复杂度 \(O\left(n^2\right)\) ，对于 \(n\le 10^5\) 显然会TLE

for (int i=1;i<=n;i++)
    for (int j=1;j<i;j++)
        ans=min(ans,get(A[i].x,A[i].y,A[j].x,A[j].y));

算法2（贪心）

将 \(x\) ， \(y\) 分别升序降序排序（ \(4\) 种方式），每一次求出相邻元素的距离，取最小值

时间复杂度 \(O\left(nlogn\right)\) ，但仔细思考发现会有反例（对于数据比较弱的还是能拿很多分的）

inline bool cmp0(const DATA &u,const DATA &v){return u.x<v.x||(u.x==v.x&&u.y<v.y);}
inline bool cmp1(const DATA &u,const DATA &v){return u.x<v.x||(u.x==v.x&&v.y<u.y);}
inline bool cmp2(const DATA &u,const DATA &v){return v.x<u.x||(u.x==v.x&&u.y<v.y);}
inline bool cmp3(const DATA &u,const DATA &v){return v.x<u.x||(u.x==v.x&&v.y<u.y);}
void solve(){for (int i=2;i<=n;i++) ans=min(ans,get(A[i].x,A[i].y,A[i-1].x,A[i-1].y));}
sort(A+1,A+1+n,cmp0); solve();
sort(A+1,A+1+n,cmp1); solve();
sort(A+1,A+1+n,cmp2); solve();
sort(A+1,A+1+n,cmp3); solve();

算法3（分治）

将 \(x\) 排好序，利用分治将序列分成左右两部分将问题划分成更小的子问题，考虑如何合并左右两

部分，不妨枚举左边的点，很显然如果 \(A_i\) 距离中间的点超过了已经求出来的最小值 \(d\) ，就直

接舍去，只考虑距离中间小于 \(d\) 的点，最多可能有 \(n\) 个点，合并时间最坏情况下为 \(n^2\) ，

但是，每个点具有以下稀疏的性质，对于任意一点，另一个点必定落在一个 \(d\times 2d\) 的矩形

中，故最多只需检查6个点

时间复杂度 \(O\left(nlognlogn\right)\) ，对于 \(n\le 10^5\) 完全可以

void solve(int l,int r){
    if (l>=r) return;
    int mid=l+r>>1;
    solve(l,mid),solve(mid+1,r);
    double S=A[mid].x;
    int nl=0,nr=0;
    for (int i=l;i<=mid;i++) if (S-A[i].x<=ans) L[++nl]=A[i];
    for (int i=mid+1;i<=r;i++) if (A[i].x-S<=ans) R[++nr]=A[i];
    sort(L+1,L+1+nl,cmpy),sort(R+1,R+1+nr,cmpy);
    int top=1;
    double d=ans;
    for (int i=1;i<=nl;i++){
        for (;top<=nr&&L[i].y-d>R[top].y;++top);
        for (int j=top;j<=top+5&&j<=nr;j++) ans=min(ans,get(L[i].x,L[i].y,R[j].x,R[j].y));
    }
}