最近点对问题（分治法）

系统管理员 2022-04-13 06:12 269阅读 0赞

**问题：**平面最近点对问题是指：在给出的同一个平面内的所有点的坐标，然后找出这些点中最近的两个点的距离.

**代码：**

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <cmath>  
    #include <algorithm>  
    using namespace std;
    const double inf = 1e20;
    const int maxn = 100005;
    
    struct Point{
        double x, y;
    }point[maxn];
    
    int n, mpt[maxn];
    
    
    //以x为基准排序
    bool cmpxy(const Point& a, const Point& b){
        if (a.x != b.x)
            return a.x < b.x;
        return a.y < b.y;
    }
    
    bool cmpy(const int& a, const int& b){
        return point[a].y < point[b].y;
    }
    
    double min(double a, double b){
        return a < b ? a : b;
    }
    
    double dis(int i, int j){
        return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
    }
    
    double Closest_Pair(int left, int right){
        double d = inf;
        if (left == right)
            return d;
        if (left + 1 == right)
            return dis(left, right);
        int mid = (left + right) >> 1;
        double d1 = Closest_Pair(left, mid);
        double d2 = Closest_Pair(mid + 1, right);
        d = min(d1, d2);
        int i, j, k = 0;
        //分离出宽度为d的区间  
        for (i = left; i <= right; i++){
            if (fabs(point[mid].x - point[i].x) <= d)
                mpt[k++] = i;
        }
        sort(mpt, mpt + k, cmpy);
        //线性扫描  
        for (i = 0; i < k; i++){
            for (j = i + 1; j < k && point[mpt[j]].y - point[mpt[i]].y<d; j++){
                double d3 = dis(mpt[i], mpt[j]);
                if (d > d3)    d = d3;
            }
        }
        return d;
    }
    
    int main(){
        while (~scanf("%d", &n) && n){
            for (int i = 0; i < n; i++)
                scanf("%lf %lf", &point[i].x, &point[i].y);
            sort(point, point + n, cmpxy);
            printf("%.2lf\n", Closest_Pair(0, n - 1) / 2);
        }
        return 0;
    }