平面最近點對

暴力的話，時間複雜度是 O ( n 2 ) O(n^2) O(n2)

是以我們考慮分治

首先按 x x x排序

接着以中間，分成兩個區域

分别計算最近點對

然後取兩者較小的值 d d d

接着考慮一個在左邊一個字右邊的點對

A A A點的最近點對，隻會在右邊這個 d × 2 d d \times 2d d×2d的矩形區域裡

因為向上 d d d，向下 d d d，向右 d d d

（當然你要說隻會在以 A A A為圓心， d d d為半徑的圓裡也可以，隻是矩形好算）

接着證明這個矩形裡，最多隻有6個點

把這個矩形分成如下的6個小矩形

假設超過了6個點，根據抽屜原理，必然有一個小矩形有2個點

但是每個小矩形的對角線的距離

( d 2 ) 2 + ( 2 d 3 ) 2 = 5 d 6 < d \sqrt{(\frac{d}{2})^2 + (\frac{2d}{3})^2} =\frac{5d}{6}<d (2d​)2+(32d​)2

​=65d​<d

與右邊區域的最近點對距離為 d d d沖突

是以隻有6個點

那麼時間複雜度為

排序 O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2​n)

分治 T ( n ) = 2 T ( n 2 ) + 6 n = 2 T ( n 2 ) + O ( n ) T(n)=2T(\frac{n}{2})+6n=2T(\frac{n}{2})+O(n) T(n)=2T(2n​)+6n=2T(2n​)+O(n)

由主定理 T ( n ) = O ( n log ⁡ 2 n ) T(n)=O(n\log_2 n) T(n)=O(nlog2​n)

是以總的複雜度是 O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2​n)

OJ

洛谷P1257 ，P1429

做法其實大緻和上面将的差不多

隻是找一個點在左邊一個點在右邊的點對的時候，

是直接将 m i d mid mid為中心左邊 d d d,右邊 d d d的點找出來，排個序，然後比。

總的時間複雜度其實差不多

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<double,double> P;
const int N=200005;
P p[N];//坐标
int n,temp[N];
bool cmpX(const P& a,const P& b){
    return a.first<b.first;
}
bool cmpY(int a,int b){
    if(p[a].second!=p[b].second)return p[a].second<p[b].second;
    return p[a].first<p[b].first;
}
double get_distance(const P& a,const P& b){
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
double solve(int left,int right){
    double d=2e9;
    if(left==right)return d;
    else if(left+1==right)return get_distance(p[left],p[right]);
    int mid=(left+right)>>1;
    d=min(solve(left,mid),solve(mid+1,right));
    int t=0;
    //找以mid為中心左右距離d的
    for(int i=left;i<=right;++i){
        //注意這裡temp是複制下标，而不是坐标，複制坐标容易T（因為我就T了
        if(fabs(p[i].first-p[mid].first)<d)
            temp[t++]=i;
    }
    sort(temp,temp+t,cmpY);
    for(int i=0;i<t-1;++i){
        for(int j=i+1;j<t&&p[temp[j]].second-p[temp[i]].second<d;++j){
            d=min(d, get_distance(p[temp[i]],p[temp[j]]));
        }
    }
    return d;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        double x,y;
        scanf("%lf%lf",&x,&y);
        p[i]=make_pair(x,y);
    }
    sort(p,p+n,cmpX);
    printf("%.4lf\n",solve(0,n-1));
    return 0;
}