题解 洛谷 P1257/P1429/P7883 平面最近点对

本文主要介绍分治法

P1257

因为数据范围太小从而可以$n^2$水过，所以只评了个橙，那么直接$n^2$做就可以了

P1429/P7883

这两道题的数据范围都在$10^5$，所以我们期望的时间复杂度是$O(nlogn)$，这时候我们就不要充分发扬人类智慧了（，果断使用分治

分治策略

考虑将这些点划分成若干区间进行比较，因为点是乱序的，所以我们先对所有点按照$x$坐标从小到大进行排序，排好序以后从中间序号的点来二分整个$xOy$系，递归二分若干次后，我们只需要对三种情况的点进行比较就可以了

1.两个点都在$mid$左边

2.两个点都在$mid$右边

3.一个在左边，一个在右边

诶！我们发现这种对比方式是不是在哪里见过呀，没错，就是逆序对！那么这个题可以说和逆序对没有什么关系。但是我们在分治的时候采取的策略是有相似之处的，前两种情况只需要用最普通的递归就可以轻松解决，像这样：

dis = min(solve(l,mid), solve(mid + 1, r));

在实现的时候我们可以发现我们先处理出来了在各自一边的最近点对的距离$dis$,那么接下来我们其实就是要把跨区间的点对的$dis$和当前的$dis$比较然后取$min$，所以我们把距离中线$mid$水平距离小于$dis$的点都取出来扔进一个容器里（你看这个数组它就很好用），很容易证明水平距离大于$dis$的点不可能满足条件（直角三角形斜边长大于直角边总会用吧）

$Well $ $Done!$ 我们离成功只剩一步之遥

将这些点取出来以后，我们先对这些点按照$y$进行排序，然后枚举这些点，分别以每个点为圆心，半径为$dis$画圆，然后把圆内的点与圆心的距离和$dis$比较取较小的即可。请注意：这里的$dis$是实时更新的，所以圆的半径在不断缩小或者不变。

于是这道题就做完了，下面是$P1429$的$AC$代码，$P7883$只要在它的基础上把$long$ $double$改成$long$ $long$即可

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <algorithm>
#define LD long double
using namespace std;

namespace SHAWN {
    const int N = 2e5 + 7;
    const LD INF = 1e18;
    struct node { LD x, y; }pt[N];
    int que[N];
    int n;
    bool cmp1 (node a, node b) { return a.x < b.x; }
    bool cmp2 (int a, int b) { return pt[a].y < pt[b].y; }
    LD getlen(node a, node b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }
    LD solve(int l, int r)  {
        if (l == r) { return INF; }
        if (l == r - 1) { return getlen(pt[l], pt[r]); }
        int mid = l + ((r - l) >> 1);
        LD dis = min(solve(l, mid), solve(mid + 1, r));
        int idx = 0;
        for (int i = l; i <= r; ++i) {
            if ((pt[mid].x - pt[i].x) * (pt[mid].x - pt[i].x) < dis) {
                que[++idx] = i;
            }
        }
        sort(que + 1, que + idx + 1, cmp2);
        for (int i = 1; i <= idx; ++i) {
            for (int j = i + 1; j <= idx && ((pt[que[i]].y - pt[que[j]].y) * (pt[que[i]].y - pt[que[j]].y)) < dis; ++j) {
                dis = min(dis, getlen(pt[que[i]], pt[que[j]]));
            }
        }
        return dis;
    }
    int work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) { cin >> pt[i].x >> pt[i].y; }
        sort(pt + 1, pt + n + 1, cmp1);
        cout << fixed << setprecision(4) << sqrt(solve(1, n)) << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}