洛谷-P1257 平面上的最接近点对（分治）¶

洛谷-P1257 平面上的最接近点对（分治）¶

题目描述¶

给定平面上 n*n* 个点，找出其中的一对点的距离，使得在这 n*n* 个点的所有点对中，该距离为所有点对中最小的。

输入格式¶

第一行一个整数 n*n*，表示点的个数。

接下来 n*n* 行，每行两个实数 x,y*x*,y ，表示一个点的行坐标和列坐标。

输出格式¶

仅一行，一个实数，表示最短距离，四舍五入保留 44 位小数。

输入输出样例¶

输入 #1

输出 #1

1.0000

说明/提示¶

数据规模与约定¶

对于 100\%100% 的数据，保证 1 \leq n \leq 10^41≤n≤104，0 \leq x, y \leq 10^90≤x,y≤109，小数点后的数字个数不超过 66。

#include <bits/stdc++.h>

using namespace std;

int n;
struct Node
{
    double x, y;
    bool operator<(const Node & obj) const
    {
        return x < obj.x || (x == obj.x && y < obj.y);
    }
};
vector<Node> seq(10005);
vector<int> tmp(10005);

inline bool cmp(int i, int j)
{
    return seq[i].y < seq[j].y;
}

inline double dis(int i, int j)
{
    double xSquare = (seq[i].x - seq[j].x) * (seq[i].x - seq[j].x);
    double ySquare = (seq[i].y - seq[j].y) * (seq[i].y - seq[j].y);
    return sqrt(xSquare + ySquare);
}

//PCPP: plane closest point pair
double PCPP(int left, int right)
{
    if (left == right) return INT_MAX * 1.0;
    if (left + 1 == right) return dis(left, right);
    //分别计算左右部分的最近点对
    int mid = left + ((right - left) >> 1);
    double d1 = PCPP(left, mid);
    double d2 = PCPP(mid + 1, right);
    double res = min(d1, d2);
    //计算横跨左右部分的最近点对
    int cnt = 0;
    for (int i = left; i <= right; ++i) {
        if (fabs(seq[i].x - seq[mid].x) <= res) 
            tmp[cnt++] = i;
    }
    //根据纵坐标对下标进行排序
    sort(tmp.begin(), tmp.begin() + cnt, cmp);

    for (int i = 0; i < cnt; ++i) {
        //如果纵坐标差值大于res，无需进行计算
        for (int j = i + 1; j < cnt && seq[tmp[j]].y - seq[tmp[i]].y < res; ++j) {
            double d3 = dis(tmp[i], tmp[j]);
            res = min(res, d3);
        }
    }

    return res;
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i].x >> seq[i].y;
    }

    sort(seq.begin(), seq.begin() + n);
    cout << fixed << setprecision(4) << PCPP(0, n - 1) << endl;


    return 0;
}

分治的思想是将整个数组一分为二，分别计算每个组内的最近点对，然后再去计算跨越左右界限的点对，看是否存在比已知点对距离更小的点对。首先就是根据横坐标对数据进行排序。函数PCPP的输入参数是需要计算部分的左右下标。

在进行划分之前需要进行边界处理，因为分治法是递归的去处理，一个很重要的环节就是递归何时终止，如果递归到数组内只有一个元素，那么就返回一个较大的数值，这时认为另一个点在无穷远处。如果只有两个点的时候，直接计算两个点的距离即可。

然后将数组一分为二，分别计算每个组内的最近点对距离。然后处理横跨左右的部分。

左右递归计算后最近点对结果为2，然后就是计算跨越中线的最近点对，这里只需要把横坐标差值小于res的部分进行统计，因为如果横坐标差值都大于res，加上纵坐标，肯定不是最近点对。用一个数组tmp存储这些点的下标，接下来就是看数组内的点对之间的距离，看起来需要暴力计算。但是可以根据其纵坐标进行排序，这样如果两个点的纵坐标差值大于res了，从这个点以后的都无需计算了。如果存在小于res的点对，那么就更新res即可。

随机旋转解法

#include <bits/stdc++.h>

using namespace std;

int n;
struct Node
{
    double x, y;
    bool operator<(const Node & obj) const
    {
        return x < obj.x || (x == obj.x && y < obj.y);
    }
};
vector<Node> seq(200005);
double res = INT_MAX * 1.0;
const double PI = 2 * asin(1);

inline double dis(int i, int j)
{
    double xSquare = (seq[i].x - seq[j].x) * (seq[i].x - seq[j].x);
    double ySquare = (seq[i].y - seq[j].y) * (seq[i].y - seq[j].y);
    return sqrt(xSquare + ySquare);
}

void DFS(int start)
{
    //计算从start往后5个点，不足就只计算到结尾
    int len = min(start + 5 + 1, n);
    for (int i = start + 1; i < len; ++i) {
        if (seq[i].x - seq[start].x > res) break;
        res = min(res, dis(start, i));
    }
}

void rotate(double arc)
{
    //根据旋转公式进行旋转
    for (int i = 0; i < n; ++i) {
        double xPos = seq[i].x, yPos = seq[i].y;
        seq[i].x = xPos * cos(arc) - yPos * sin(arc);
        seq[i].y = xPos * sin(arc) + yPos * cos(arc);
    }
}

//PCPP: plane closest point pair
//times: 进行随机旋转的次数
void PCPP(int times)
{
    for (int i = 0; i < times; ++i) {
        //根据横坐标进行排序
        sort(seq.begin(), seq.begin() + n);
        for (int j = 0; j < n; ++j) DFS(j); //计算每个点后五个点的最小距离
        if (i != times - 1) { //最后一次不需要旋转
            //初始化随机种子
            srand(time(NULL));
            //产生一个0-359的角度，然后转成弧度
            rotate((rand() % 360) * 1.0 / 360 * PI);
        }
    }   
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i].x >> seq[i].y;
    }

    PCPP(2);
    cout << fixed << setprecision(4) << res << endl;

    return 0;
}