「Raid」袭击

形式化题目

平面上给定 $n$ 个"红点"（核电站）与 $n$ 个"蓝点"（特工），坐标为整数且 $0 \leqslant X, Y \leqslant 10^9$ 。求任意一个红点与任意一个蓝点之间的最小欧氏距离，保留三位小数。多组数据。

注意：题目求的不是全部 $2n$ 个点的最近点对——红点与红点、蓝点与蓝点之间的距离一律不计入答案。

正解

思路

一句话本质：这是经典的"最近点对分治"的二色版本——分治框架原封不动，只在两处动刀：合并时跳过同色点对，并把"当前最优值"作为上界传进递归，而不是让左右两半各自算出只关于自己颜色的 $d$ 。

先看朴素做法：枚举每一对（电站，特工）， $n = 10^5$ 时约 $10^{10}$ 次距离计算，完全不可行。 $O(n^2)$ 挡在这里，必须找到与最近点对同阶的做法。

第一步：从样例确认"跨色"这个约束。 样例一中电站占据单位正方形四个角，特工占据 (2,2) 到 (3,3) 的小正方形。全部 8 个点的最近点对距离是 $1.000$ （电站正方形的边），而期望输出是 $1.414$ ——那是跨过两块区域的最短距离。这证实：同色点对再多、再近，也不许更新答案。

第二步：套用最近点对分治的骨架。 把所有点（带上颜色标记）按 $x$ 排序，从中间切一刀，分界线为 $x = mid\_x$ 。任意跨色点对只有三类：两点都在左半、都在右半、一左一右跨界。前两类交给递归，剩下的问题是"跨界点对怎么不枚举也能查完"。

经典分析在这里照常生效：设当前最优平方距离为 $best$ ，若某个跨界点对要打败它，则

dx^2 \leqslant dx^2 + dy^2 < best \quad\Rightarrow\quad dx^2 < best

所以两个端点的 $x$ 都落在分界线两侧宽度为 $\sqrt{best}$ 的窄条内；同理 $dy^2 < best$ 。把窄条内的点按 $y$ 升序排好，对每个点 $p$ 只向后扫描到 $(y_q - y_p)^2 \geqslant best$ 为止——后面的点 $y$ 只会更大，全部可以放弃。

第三步：二色版本真正的坑—— $d$ 必须是"跨色的 $d$ "。 经典写法里 $d = \min(\text{左半答案}, \text{右半答案})$ 。但本题左右两半"自己内部的最近点对"可能是同色的，而且同色点可以无限密集地挤在一起：假如左半里 99999 个电站挤成一团， $\min$ 算出的 $d$ 就约为 0，窄条窄成一条缝，真正的跨界点对全被剪掉了——错解。

修法是把上界下传：递归函数写成 divide(pts, best) -> (best', 按y有序的点)。从根往下，best 一路带着"到目前为止已知的跨色最优平方距离"进入子问题；子问题里每发现一个更近的跨色点对就立刻收紧它，再传给更深处。这样剪枝裁掉的永远只是"不优于当前跨色答案"的点对，绝不会漏。代价是鸽巢原理的"每点至多比较 7 个后继"不再成立（那要求每个 $d \times d$ 方块内点数有限，而同色点不受限），所以内层循环必须老老实实用 $(y_q - y_p)^2 \geqslant best$ 就 break 的窗口扫描——好在同色点越挤，break 反而触发得越早，最坏情况不会劣化。

第四步：初始上界与实现细节。

递归进入前，用 random.choices 随机抽 1000 对（电站，特工），取最小平方距离当初始 best。这保证 best 一开始就是某个真实跨色点对的距离（从而 $n=1$ 这类"递归里根本没有跨色比较机会"的边界也天然正确），剪枝半径也一开始就有限。
递归返回按 $y$ 升序的点列表，两半 merge 归并成整体有序，每层线性，避免每层重新排序。
全程用整数平方距离比较（ $dx^2 + dy^2 < 2 \times 10^{18}$ ，int 无忧），只在输出前开一次方，%.3f 格式化，精度无忧。

代码

Python 版：

python

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100#!/usr/bin/env python3
# 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-10-01 10:39
# update_at: 2026-10-01 10:39

import random
import sys
from operator import itemgetter

STATION = 0  # 颜色编码：0 = 核电站
AGENT = 1    # 颜色编码：1 = 特工
SAMPLE_K = 1000  # 开局随机抽多少对跨色点当初始上界


def dist_sq(p: tuple, q: tuple) -> int:
    """两点距离的平方：全程用整数比较，避免开方误差。"""
    dx = p[0] - q[0]
    dy = p[1] - q[1]
    return dx * dx + dy * dy


def merge_by_y(a: list, b: list) -> list:
    """归并两个已按 y 升序的列表，O(len(a)+len(b))。"""
    out = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i][1] <= b[j][1]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]


def divide(pts: list, best: int) -> tuple[int, list]:
    """分治：pts 已按 (x, y) 排序。

    返回 (跨色最小距离平方的当前上界 best, 该批点按 y 升序的列表)。
    best 一路当作"剪枝下限"传入传出：只会变小，不会漏掉更优的跨色点对。
    """
    n = len(pts)
    if n < 2:
        return best, pts
    mid = n // 2
    mid_x = pts[mid][0]  # 分割竖线：左半 x ≤ mid_x ≤ 右半 x

    best, left = divide(pts[:mid], best)
    best, right = divide(pts[mid:], best)
    by_y = merge_by_y(left, right)  # 两半各自已按 y 有序，归并免得重复排序

    # 更近的跨色点对 (l, r) 必有 l.x、r.x 都落在分割线附近：
    # 若 mid_x - l.x ≥ √best，则距离 ≥ r.x - l.x ≥ mid_x - l.x ≥ √best，不可能更优
    strip = [p for p in by_y if (p[0] - mid_x) ** 2 < best]

    # strip 已按 y 升序；q 在 p 之后且 y 己 ≥ √best 时，后面的点只会更远
    m = len(strip)
    for i in range(m):
        px, py, pc = strip[i]
        for j in range(i + 1, m):
            qx, qy, qc = strip[j]
            if (qy - py) ** 2 >= best:
                break
            if qc == pc:  # 同色点对（电站-电站 / 特工-特工）不计入答案
                continue
            best = min(best, dist_sq(strip[i], strip[j]))
    return best, by_y


def closest_pair(stations: list, agents: list) -> float:
    """返回任一电站到任一特工的最小欧氏距离。"""
    pts = [(x, y, STATION) for x, y in stations] + [(x, y, AGENT) for x, y in agents]
    pts.sort()

    # 先随机抽些跨色点对估个上界：让分治一开始就有有限的剪枝半径，
    # 也避免"整批点同色/跨色对很少"时 strip 内层循环失去 break 依据
    pairs = zip(random.choices(stations, k=SAMPLE_K), random.choices(agents, k=SAMPLE_K))
    best = min(dist_sq(p, q) for p, q in pairs)
    best, _ = divide(pts, best)
    return best ** 0.5


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        stations = [(next(data), next(data)) for _ in range(n)]
        agents = [(next(data), next(data)) for _ in range(n)]
        out.append(f"{closest_pair(stations, agents):.3f}")

    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113/**
 * 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-10-06 14:36
 * update_at: 2026-10-06 14:36
 */
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

// 二色最近点对：核电站-特工才算答案，同色点对一律跳过。
// 套用经典最近点对分治骨架，关键差异是把跨色最优平方距离 best
// 作为参数一路"下传"递归（而不是取左右两半各自答案的 min），
// 否则同色点挤成一团时会把窄条剪成一条缝、漏掉真正的跨色点对。

const int MAXN = 200005; // 每组最多 2n 个点，n <= 100000

struct P {
    ll x, y;
    int c; // 颜色：0 = 核电站，1 = 特工
};

P a[MAXN];     // a[1..2n] 存本组所有点，进入递归前按 x 排序，递归会把区间整理成按 y 有序
P tmp[MAXN];   // 归并两半用的临时数组
P strip[MAXN]; // 距分割线水平距离的平方 < best 的窄条内的点（按 y 升序）

bool cmp_p(const P &u, const P &v) {
    if (u.x != v.x) return u.x < v.x;
    return u.y < v.y;
}

// 两点距离的平方：全程用整数比较，坐标 1e9 级别时平方和 < 2^63，不会溢出
ll sq_dist(const P &u, const P &v) {
    ll dx = u.x - v.x, dy = u.y - v.y;
    return dx * dx + dy * dy;
}

// 分治处理 a[l..r)：best 是当前已知的跨色最小平方距离，只会变小、不会漏解。
// 返回更新后的 best，同时把 a[l..r) 整理成按 y 升序，供上层归并。
ll divide(int l, int r, ll best) {
    if (r - l <= 1) return best; // 0 或 1 个点，区间内无从比较
    int mid = (l + r) / 2;
    ll midx = a[mid].x; // 分割竖线 x = midx，必须在递归前记下（递归会打乱 a）

    best = divide(l, mid, best);
    best = divide(mid, r, best);

    // 归并两半（各自已按 y 升序），使 a[l..r) 整体按 y 升序
    int p = l, q = mid, t = l;
    while (p < mid && q < r) {
        if (a[p].y <= a[q].y) tmp[t++] = a[p++];
        else tmp[t++] = a[q++];
    }
    while (p < mid) tmp[t++] = a[p++];
    while (q < r) tmp[t++] = a[q++];
    for (int i = l; i < r; i++) a[i] = tmp[i];

    // 更近的跨色点对两端点的 x 都必须落在分割线两侧宽 sqrt(best) 的窄条内：
    // 否则 dx >= sqrt(best)，距离不可能更优。strip 已按 y 升序。
    int m = 0;
    for (int i = l; i < r; i++) {
        ll dx = a[i].x - midx;
        if (dx * dx < best) strip[m++] = a[i];
    }

    // 窗口扫描：对每个点只向后看，一旦 y 差平方 >= best 就 break
    // （后面的点 y 只会更大，全部可以放弃）；同色点对直接跳过。
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            ll dy = strip[j].y - strip[i].y;
            if (dy * dy >= best) break;
            if (strip[i].c == strip[j].c) continue; // 同色不计入答案
            best = min(best, sq_dist(strip[i], strip[j]));
        }
    }
    return best;
}

int main() {
    int T;
    scanf("%d", &T);
    srand(20261006); // 固定随机种子，行为可复现
    while (T--) {
        int n;
        scanf("%d", &n);
        // 前 n 个是核电站（a[1..n]），后 n 个是特工（a[n+1..2n]）
        for (int i = 1; i <= 2 * n; i++) {
            scanf("%lld%lld", &a[i].x, &a[i].y);
            a[i].c = (i <= n) ? 0 : 1;
        }

        // 开局随机抽 1000 对（电站, 特工），取最小平方距离当初始上界：
        // 保证 best 一开始就是某个真实跨色点对的距离（n=1 的边界也天然正确），
        // 剪枝半径从一开始就有限
        ll best = -1;
        for (int k = 0; k < 1000; k++) {
            int i = rand() % n + 1;
            int j = rand() % n + 1;
            ll d = sq_dist(a[i], a[n + j]);
            if (best == -1 || d < best) best = d;
        }

        sort(a + 1, a + 2 * n + 1, cmp_p);
        best = divide(1, 2 * n + 1, best);
        printf("%.3f\n", sqrt((double)best));
    }
    return 0;
}

复杂度

按 $x$ 排序一次 $O(n \log n)$ ；递归 $O(\log n)$ 层，每层归并 $O(n)$ 、窄条收集与窗口扫描均摊 $O(n)$ ，总计 $O(n \log n)$ 。空间上递归切片为 $O(n \log n)$ 。 $n = 10^5$ 、坐标 $10^9$ 级别下，Python 常数偏大，存在 TLE 风险（本仓库教学解允许）；同样的骨架用 C++ 实现（long long 存平方距离）可以稳过 1 秒限制。

图示解析

样例一：为什么答案是 1.414

下图画出样例一的 8 个点（◆ 核电站，★ 特工）：

text

1
2
3
4
5
6y
3 |          ★     ★
2 |          ★     ★
1 |  ◆     ◆
0 |  ◆     ◆
    0     1     2     3   x

观察重点：全局最近点对是 ◆—◆（距离 1.000），但它是同色的，不许计入答案。跨色最近的一对是 ◆(1,0) — ★(2,1) 之类，距离 $\sqrt{2} \approx 1.414$ 。这就是样例输出——题目在颜色维度上做了过滤，解法也必须跟着过滤。

分治合并：窄条内的窗口扫描

text

1
2
3
4
5
6
7
8
9
10
11            mid_x
              │
   左半  ┌────┼────┐  右半
         │ 窄条: (x-mid_x)² < best │
         │    │    │
         │    │  q ● │   ← 与 p 跨色，检查
         │    │      │
         │  p ●      │
         └────┼────┘
              │
   窄条外的点：dx² ≥ best，距离不可能更优，直接不收集

观察重点：窄条按 $y$ 升序排列后，对每个 $p$ 只向后看，一旦 $(y_q - y_p)^2 \geqslant best$ 就停止—— $y$ 差是距离的一个下界，后面的点只会更远。与经典版本不同，这里 $p$ 的后继中同色点直接 continue，而 best 是从更上层传下来的跨色最优值，保证剪枝既紧又不漏。

总结

本题是二色最近点对：电站-特工才计答案，同色点对一律跳过。
分治骨架与经典最近点对一致：按 $x$ 切半、递归、窄条 + $y$ 升序窗口扫描。
关键差异是把跨色最优值 best 作为参数下传递归，而不是用左右两半各自的 $\min$ ——否则同色点密集时 $d$ 会失真、窄条漏解；相应地，内层循环用"y 差平方 $\geqslant$ best 即 break"的窗口扫描代替定长 7 后继。
比较全程用整数平方距离，只在输出前开一次方；随机抽样 1000 对提供初始上界，同时覆盖 $n=1$ 的边界。
总复杂度 $O(n \log n)$ 。

「Raid」 袭击

目录

形式化题目

正解

思路

代码

复杂度

图示解析

样例一：为什么答案是 1.414

分治合并：窄条内的窗口扫描

总结