平面内距离最短点对

题目描述

• 给你一系列二维点对，让你求其中的最短距离

思路

• 分治，分别求分界点左边的最短距离和右边的最短距离，然后看左边和右边之间的点有无小于左右最短距离的。只需要比较距离中心轴为d的区域内的点对即可，可以证明该区域内一个最多只需要和6个点计算距离，复杂度为6n。
• 距离解析参考：Link

代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

static bool sort_by_x(vector<double> coor1, vector<double>coor2)
{
    return coor1[0]<coor2[0];
}

static bool sort_by_y(vector<double> coor1, vector<double> coor2)
{
    return coor1[1] < coor2[1];
}

double getDistance(vector<double> coor1, vector<double> coor2)
{
    return sqrt(pow(coor1[0]-coor2[0],2) + pow(coor1[1]-coor2[1],2));
}

double minDistance(vector<vector<double>>& coords, int start, int end)
{
    if (end-start==1) //只有两个点 
    {
        return getDistance(coords[start], coords[end]);
    }
    else if(end-start==2) //只有三个点
    {
        double t1 = getDistance(coords[start], coords[start+1]);
        double t2 = getDistance(coords[start], coords[end]);
        double t3 = getDistance(coords[start+1], coords[end]);
        return min(min(t1, t3), t2);
    }
    else //分治，左最小，右最小，以及全局最小
    {
        int mid = start + (end-start)/2;
        double l_min = minDistance(coords, start, mid);
        double r_min = minDistance(coords, mid+1, end);
        double d = min(l_min, r_min);

        //得到所有距离中心分割点小于d的坐标
        vector<vector<double>> res;
        for(int i=0;i<coords.size();i++)
        {
            if(abs(coords[i][0]-coords[mid][0]) <= d)
                res.push_back(coords[i]);
        }

        //按照y坐标排序
        sort(res.begin(), res.end(), sort_by_y);

        //在res中分别计算是否有距离小于d的点对，对于每个点，只需要它与距离它宽为d高为2d的矩形区域内点做对比；可以证明对于每个点，它只需要与6个点求距离
        for(int i=0;i<res.size();i++)
        {
            for(int j=i+1;j<res.size();j++)
            {
                if(res[j][1]-res[i][1]>d)
                    break;
                if(getDistance(res[i], res[j])<d)
                {
                    d = getDistance(res[i], res[j]);
                }
            }
        }
        return d;
    }
}


int main()
{
    int n;
    cin>>n;
    vector<vector<double>> coords(n, vector<double>(2, 0));
    for(int i=0;i<n;i++)
        cin>>coords[i][0]>>coords[i][1];
    //按照x坐标升序
    sort(coords.begin(), coords.end(), sort_by_x);
    double res = minDistance(coords, 0, coords.size()-1);
    cout<<res;
    system("pause");
    return 0;
}