暴力求解¶

先求第一个点到其他点的最短距离，再求第二个点到其他点的最短距离，依此类推。时间复杂度 $O(n^2)$ ，只要数据大于 $10^3$ 肯定超时。

分治算法¶

洛谷-P1257 平面上的最接近点对
洛谷-P1429 平面最近点对（加强版）

这里借鉴**syksykCCC**在洛谷题解里的解释，图片也援引于洛谷。

比如这样一组输入：

共十个点，将其画在直角坐标系里。

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

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

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

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

时间复杂度 $O(n \log n \log n)$ ，空间复杂度 $O(n)$ 。

#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);
vector<int> tmp(200005);


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;
}

随机旋转¶

算法基本步骤：

随机旋转
按横坐标排序后枚举每个点与其后面5个点的距离取最小值更新答案。

以点 $(x_2, y_2)$ 为中心进行旋转： $$ x_1 = (x_1 - x_2) \times \cos \theta - (y_1 - y_2) \times \sin \theta + x_2 \ y_1 = (x_1 - x_2)\times \sin \theta + (y_1 - y_2) \times \cos \theta + y_2 $$ 其中 $\theta$ 是弧度表示。现在看不旋转去寻找每个点后面五个点的距离最小值：

如图A点会与B、C、D、E、F（按顺序）更新答案，但是G应该是离A最近的点。旋转可以很好地解决这个问题。如下图：A点会与G、F、D、B、C（按顺序）更新答案。两次旋转即可得到结果。

#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;
}

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。

典型题目：

洛谷-P1257 平面上的最接近点对
洛谷-P1429 平面最近点对（加强版）
洛谷-P6247 [SDOI2012]最近最远点对
HDU 1007
POJ 3714 Raid
CGL_5_A closest pair