p1429 平面最近点对

一时失言乱红尘 2022-05-13 13:24 196阅读 0赞

题意：给平面n个点，求最近的两个点的距离。

思路：运用分治思想，对于n个点，可以分成T(n/2)+T(n/2)的规模，分界线是x坐标的中位数，

假设左边点集合为s1, 右边点集合为s2，那么最小值存在于以下三种情况中。

1.s1中任意两点距离的最小距离

2.s2中任意两点距离的最小距离

3.s1中的点到s2中的点的距离的最小距离

前两部分可以一直分治到底。

第三部分

对于左边每一个点，右边和他产生距离更小的点只能存在于

2d\*d的矩形中，而对于2d/3\*d/2的矩形，只可能存在一个点，所以点数最多不超过6个

这就使每一层的时间降到O（n），所以总复杂度为O(nlogn)

#include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    const double INF=1e18;
    const double eps=1e-10;
    
    struct Point{
        double x, y;
        bool operator < (const Point t) const{
            return x<t.x;
        }
    }p[N], b[N];
    int n;
    inline double dis(Point a, Point b){
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    int dcmp(double x){
        if(fabs(x)<eps) return 0;
        return x<0?-1:0;
    }
    bool cmp(Point p1, Point p2){
        return p1.y<p2.y;
    }
    
    double cdq(int l, int r){
        double d=INF;
        if(l>=r)return d;
        int mid=(l+r)>>1;
        d=min(d, cdq(l, mid)); d=min(d, cdq(mid+1, r));
    
        int t=0;
        for(int i=l; i<=r; i++){//选出距离中位线不超过d的点
            if(dcmp(d-fabs(p[i].x-p[mid].x))>=0)
                    b[++t]=p[i];
        }
        sort(b+1, b+1+t, cmp);
        for(int i=1; i<=t; i++){
            for(int j=i+1; j<=t && fabs(b[i].y-b[j].y)<=d; j++){//对左边每一个点，找右边y不超过d的点
                if(dis(b[i], b[j])-d<0)
                    d=dis(b[i], b[j]);
            }
        }
        return d;
    }
    
    int main(){
        scanf("%d", &n);
    
        for(int i=1; i<=n; i++){
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        sort(p+1, p+1+n);
    
        printf("%.4lf\n", cdq(1, n));
    
        return 0;
    }