平面上的最接近点对

题意

平面上 $n$ 个点（ $2 \leqslant n \leqslant 10^4$ ， $0 \leqslant x, y \leqslant 10^9$ ），求所有点对中距离最小的一对，输出距离保留 4 位小数。

思路

一句话本质：分治把"所有点对"拆成"左内部 + 右内部 + 跨界"三类。左右递归解决，跨界靠一个关键事实剪枝：距离 < d 的点对，x 差和 y 差都必须小于 d，所以跨界候选只在一条窄条里，而且窄条里每点只需和后面少数几个点比较。

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 13:00
 * update_at: 2026-08-05 13:00
 */
// brute.cpp：小数据暴力解，O(n^2) 枚举所有点对取最小距离。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n;
long long x[MAXN], y[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    double ans = 1e100;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            long long dx = x[i] - x[j], dy = y[i] - y[j];
            ans = min(ans, sqrt((double)(dx * dx + dy * dy)));
        }

    cout << fixed << setprecision(4) << ans << '\n';

    return 0;
}

暴力枚举所有 $\binom{n}{2} \approx \frac{n^2}{2}$ 个点对， $n = 10^4$ 时要算 $5 \times 10^7$ 次距离，不可行。

能不能不枚举所有点对？

把点按 $x$ 排序，从中间分成左右两半。任意点对只有三类：两端都在左半、都在右半、跨界。前两类用递归解决，问题只剩跨界点对。

跨界点对能不能剪掉大部分？

设 $d = \min(\text{左半答案}, \text{右半答案})$ 。若跨界点对距离 $< d$ ，它的 $x$ 差必须 $< d$ ：距离 $= \sqrt{dx^2 + dy^2}$ 是直角三角形的斜边，由勾股定理推论——斜边 $\geqslant$ 任意直角边——可知 $dx \leqslant \text{距离} < d$ ，所以 $dx < d$ 。所以只需检查 $x$ 落在分界线 $\pm d$ 范围内的点——一条窄条。 $d$ 通常很小，窄条很细。

窄条内还是要两两枚举吗？

不需要。窄条内的点按 $y$ 从小到大排序。对每个点 $p_i$ ，真正可能比 $d$ 更近的点 $p_j$ 一定排在它后面（ $y_j \geqslant y_i$ ），而且 $y_j - y_i$ 必须 $< d$ （ $y$ 差 $\geqslant d$ 时距离必 $\geqslant d$ ，因为斜边 $\geqslant$ 直角边 $dy$ ）。

所以对每个 $p_i$ ，只需检查排在它后面、 $y$ 差 $< d$ 的点。那这样的点有多少？

用鸽巢原理可以证明它是常数（经典分析为 6~7 个，代码中直接用 $y$ 差 $< d$ 窗口安全扫描即可，不用担心退化）。直观理解：候选点集中在以 $p_i$ 为下边界的 $2d \times d$ 矩形里，这个区域有固定大小；而左半内部任意两点距离 $\geqslant d$ （递归得到）、右半内部同样——每侧内部互不靠近。两侧各能塞进这片小区域里的点都只有寥寥几个，加起来仍是常数。

text

1
2
3
4
5
6
7候选矩形 2d × d，分成 8 个小方块
   ┌──┬──┬──┬──┐
   │  │● │  │  │  可能的候选点 p_j 分布在这片区域
   ├──┼──┼──┼──┤
   │● │  │  │  │  p_i 在这排的某个方块
   └──┴──┴──┴──┘
   ←──── 2d ────→

左右两侧各自内部的点互距 ≥ d，每侧挤不进太多点，所以每个 $p_i$ 只需看后面常数个后继。

于是合并阶段每个点只做常数次计算，不会退化为 $O(n^2)$ 。

所以合并阶段每个点只做常数次比较，总复杂度 $O(n \log n)$ 。

为什么这样不会漏掉最优解？

三类点对全覆盖：最优对在左半、右半由递归保证；跨界时，它距离 $< d$ ⇒ 必在窄条内且 $y$ 差 $< d$ ⇒ 必然被"按 y 排序后相邻扫描"检查到。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 13:00
 * update_at: 2026-08-05 13:00
 */
// 分治求最近点对：按 x 排序后递归，合并时只检查距分界线 d 以内的窄条，
// 窄条内按 y 排序后相邻比较（d×d 方块内最多常数个点，鸽巢原理）。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

struct Point {
    long long x, y;
};

int n;
Point p[MAXN];    // 按 x 排序后的点
Point tmp[MAXN];  // 窄条内的点（按 y 排序）

bool cmp_x(const Point& a, const Point& b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool cmp_y(const Point& a, const Point& b) {
    return a.y < b.y;
}

// 两点距离（平方和用 long long 计算，避免 double 精度损失）
double dist(const Point& a, const Point& b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return sqrt((double)(dx * dx + dy * dy));
}

// 分治求 p[l..r] 内的最近点对距离
double solve(int l, int r) {
    if (r - l <= 2) {   // 点数 <= 3：直接暴力枚举
        double d = 1e100;
        for (int i = l; i <= r; i++)
            for (int j = i + 1; j <= r; j++)
                d = min(d, dist(p[i], p[j]));
        return d;
    }

    int mid = (l + r) >> 1;
    double d = min(solve(l, mid), solve(mid + 1, r));

    // 合并：跨界点对若距离 < d，x 差必 < d，只收集距分界线 d 以内的点
    int cnt = 0;
    for (int i = l; i <= r; i++) {
        long long dx = p[i].x - p[mid].x;
        if (dx < 0) dx = -dx;
        if (dx < d) tmp[cnt++] = p[i];
    }

    // 窄条内按 y 排序，每个点只检查 y 差 < d 的后继点
    // 鸽巢原理：候选点在 2d×d 矩形内，每侧内部的点互距 ≥ d，
    // 每侧装不下太多点，每个点 i 最多匹配约 6~7 次后继，不退化
    sort(tmp, tmp + cnt, cmp_y);
    for (int i = 0; i < cnt; i++)
        for (int j = i + 1; j < cnt && tmp[j].y - tmp[i].y < d; j++)
            d = min(d, dist(tmp[i], tmp[j]));

    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;

    sort(p + 1, p + n + 1, cmp_x);
    cout << fixed << setprecision(4) << solve(1, n) << '\n';

    return 0;
}

复杂度

每层合并：收集窄条 $O(n)$ + 排序 $O(n \log n)$ ，递归 $\log n$ 层，总 $O(n \log^2 n)$ （ $n = 10^4$ 轻松通过；用归并可优化到 $O(n \log n)$ ）。空间 $O(n)$ 。

总结

分治最近点对是"分治 + 剪枝稀疏性"的典型：

分治正确性来自三类点对全覆盖；
效率来自两个剪枝：跨界只看 $x$ 差 $< d$ 的窄条、窄条内只看 $y$ 差 $< d$ 的相邻点；
相邻扫描的安全靠鸽巢原理（ $d \times d$ 方块内点数有常数上界）。

图示解析

这张图展示合并阶段"窄条 + 相邻扫描"为什么安全：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18分界线
   │
   │  ◇ 窄条：|x - x_mid| < d
   │  ┌───────────┐
   │  │  ●     ●  │   d
   │  │     ●     │
   │  │  ●     ●  │
   │  └───────────┘
   │
   ● 窄条外的点 x 差 >= d，距离必 >= d，直接排除

候选点在 p_i 上方、宽 2d 高 d 的矩形里，分成 8 个 (d/2)×(d/2) 小方块：
   ┌────┬────┬────┬────┐
   │  ● │    │    │    │  每个小方块最多 1 个点（对角线长 = d）
   ├────┼────┼────┼────┤  扣除 p_i 自己占的，其余最多 7 个
   │    │    │    │    │  ⇒ 点 i 最多与后面 7 个点比较
   └────┴────┴────┴────┘
        p_i

读图方法：上面说明窄条为什么是唯一的跨界候选区；下面说明为什么每个点只需检查常数个后继——任何 $d \times d$ 的窗口都装不下很多点，相邻扫描不会退化。

平面上的最接近点对

目录

题意

思路

代码

复杂度

总结

图示解析