形式化题目

平面上有两套固定位置的拦截系统 $P_1(x_1,y_1)$、$P_2(x_2,y_2)$，以及 $N$ 颗导弹。每套系统当天只能设定一次工作半径 $r_j \geqslant 0$（可取 $0$，此时只能拦截恰好同位置的导弹）。一颗导弹只要与某一套系统的距离不超过该系统半径即被拦截。要求拦截所有导弹，求代价 $r_1^2 + r_2^2$ 的最小值。

每颗导弹 $i$ 只与它到两套系统的距离平方有关。记

把导弹划分成两组——$A$ 由 1 号系统拦截、$B$ 由 2 号系统拦截——则最省的半径恰为组内最大值，代价为

空组贡献 $0$。因此题目等价于：给定 $N$ 个点对 $(d_{1i}, d_{2i})$，划分成两组，使两组各自"组内最大值"之和最小。

样例 1：$(d_1,d_2)$ 分别为 $(-3,3) \to (18,178)$、$(10,0) \to (100,0)$。前者给 1 号、后者给 2 号，代价 $18 + 0 = 18$，即答案。

样例 2：答案 $30 = 20 + 10$，即 1 号系统负责 $\{(-2,3),\,(4,0),\,(-4,-2)\}$、2 号系统负责 $\{(6,-2),\,(9,1)\}$，具体推导见下文表格。

正解

思路

朴素做法：每个导弹二选一，共 $2^N$ 种划分，不可行。

关键观察（阈值划分性质）：存在最优解，使得"交给 1 号系统的导弹"恰好是 $\{i : d_{1i} \leqslant t\}$ 这种按 $d_1$ 的阈值集合。

证明：任给一个划分，设 1 号一侧当前 $r_1^2 = \max_{i \in A} d_{1i}$。若存在导弹 $q$ 满足 $d_{1q} \leqslant r_1^2$ 却被分到 $B$，把 $q$ 挪进 $A$：$A$ 的最大 $d_1$ 不变（$d_{1q} \leqslant r_1^2$），$B$ 变小后其最大 $d_2$ 只会不变或变小，代价不增。反复挪动即得阈值形式；同时这也说明任意最优解中 $r_1^2$ 必等于 $A$ 中某颗导弹的 $d_1$（或 $0$）。 $\square$

降到一维：阈值 $t$ 恰好对应排序后的分界点——按 $d_1$ 升序排序后，把前 $k$ 颗给 1 号、后 $N-k$ 颗给 2 号，只需检查 $k = 0, 1, \dots, N$ 共 $N+1$ 个划分（$k=0$ 表示 1 号一个不拦，$k=N$ 表示 2 号一个不拦）。直接对每个 $k$ 重算两侧 max 仍是 $O(N^2)$，$N = 10^5$ 会超时。

消掉重复计算：排序后，前 $k$ 颗的 $\max d_1$ 就是第 $k$ 颗的 $d_1$ 本身（$k=0$ 记 $0$）；后 $N-k$ 颗的 $\max d_2$ 是后缀最大值 $\mathrm{suf}[k] = \max_{j \geqslant k} d_{2,(j)}$，从右往左一趟 $O(N)$ 扫出。两趟线性扫描取 $\min$ 即得答案。

下表展示样例 2 按 $d_1$ 升序排序后，每个分界点的代价（$\min$ 行加粗）：

排序后的点对依次是 $(13,73),\ (16,4),\ (20,104),\ (40,4),\ (82,10)$（分别来自导弹 $(-2,3),\ (4,0),\ (-4,-2),\ (6,-2),\ (9,1)$）。读者应重点观察：$r_1^2$ 随 $k$ 单调不减、$r_2^2$ 随 $k$ 单调不增，最小值在两者的"交点" $k=3$ 处取得，恰为题面给出的 $20 + 10 = 30$；这正是排序 + 后缀最大值能把 $O(N^2)$ 压成 $O(N \log N)$ 的原因——一侧代价由排序免费给出，另一侧代价由后缀统计量免费给出。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int x1_, y1_, x2_, y2_;
int n;
vector<pair<ll, ll> > pairs;   // (d1, d2) 距离平方

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> x1_ >> y1_ >> x2_ >> y2_;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        ll d1 = (x - x1_) * (x - x1_) + (y - y1_) * (y - y1_);
        ll d2 = (x - x2_) * (x - x2_) + (y - y2_) * (y - y2_);
        pairs.push_back(make_pair(d1, d2));
    }
    sort(pairs.begin(), pairs.end());

    // suf[i]：第 i 颗及以后全交给 2 号系统所需的 d2 后缀最大值
    vector<ll> suf(n + 1, 0);
    for (int i = n - 1; i >= 0; i--)
        suf[i] = max(pairs[i].second, suf[i + 1]);

    ll ans = 1LL << 62;
    for (int k = 0; k <= n; k++) {
        ll r1 = (k ? pairs[k - 1].first : 0);
        ll cand = r1 + suf[k];
        if (cand < ans) ans = cand;
    }
    cout << ans << "\n";
    return 0;
}

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#!/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-02 08:40
# update_at: 2026-10-02 08:40

import sys


def min_cost(pairs: list[tuple[int, int]]) -> int:
    """枚举分界点 k：前 k 颗交给 1 号系统、其余交给 2 号系统，求 r1^2 + r2^2 的最小值。"""
    n = len(pairs)

    # suf[i]：把第 i 颗及以后全交给 2 号系统所需的 r2^2，即 d2 的后缀最大值（suf[n] = 0）
    suf = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf[i] = max(pairs[i][1], suf[i + 1])

    # pairs 按 d1 升序：前 k 颗交给 1 号系统时 r1^2 就是第 k 颗的 d1；k = 0 表示 1 号不拦
    return min((pairs[k - 1][0] if k else 0) + suf[k] for k in range(n + 1))


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    x1, y1, x2, y2 = next(data), next(data), next(data), next(data)
    n = next(data)

    coords = [next(data) for _ in range(2 * n)]  # 之后 2N 个数：每颗导弹的 x, y 交替

    # 每颗导弹记为 (d1, d2)：到两套系统各自的距离平方
    pairs = sorted(
        ((x - x1) ** 2 + (y - y1) ** 2, (x - x2) ** 2 + (y - y2) ** 2)
        for x, y in zip(coords[::2], coords[1::2])
    )
    print(min_cost(pairs))


if __name__ == "__main__":
    solve()

复杂度

• 时间：排序 $O(N \log N)$ 主导，后缀最大值与分界点扫描各 $O(N)$，总计 $O(N \log N)$。
• 空间：$O(N)$，存放坐标数组、$(d_1,d_2)$ 数对与后缀数组。

总结

把"每颗导弹二选一"的指数划分，用阈值划分性质（把 $d_1$ 不超过当前 $r_1^2$ 的导弹全部挪进 1 号一侧，代价不增）压成一维分界点；按 $d_1$ 排序后，分界点一侧的代价是排序序列的末元素，另一侧的代价是 $d_2$ 后缀最大值，两趟线性扫描即可。核心不变量：$r_1^2$ 随分界点单调不减、$r_2^2$ 单调不增，最小值必在交点处。