A18.导弹拦截

题目分析

该题实际上是一个排序 + 枚举 + 后缀最大值预处理的算法。

让我拆解一下本题核心逻辑（代码附有注释）

1.排序 （固定一个维度）：先计算每颗导弹到系统1的距离平方（d1），然后按 d1 从小到大排序。

2.关键洞察 （单调性）：如果系统1的工作半径是 r1，那么它能拦截的导弹，一定是排序后靠前的那一批（即离系统1最近的若干颗）。不可能出现“系统1拦截了一颗远的，却漏掉一颗近的”这种情况，因为半径是圆形的，能覆盖远的必然能覆盖近的。

3.后缀预处理：我们枚举所有可能的分界点 i。假设系统1覆盖前 i 颗导弹（r1 = a[i].d1），那么剩下的 i+1 到 n 颗导弹就必须由系统2来拦截。此时系统2的半径 r2 必须是剩余导弹中，到系统2距离平方（d2）的最大值。代码中的 suf[i] 就是用来快速获取这个最大值的数组。

4.枚举取最小：遍历所有分界点，计算 r1^2 + r2^2，取最小值。

代码示例（懒得表示健康了）

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long d1, d2; // 到两个拦截系统的距离平方
};

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

    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int n;
    cin >> n;

    vector<Node> a(n);

    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;

        long long dx1 = x - x1, dy1 = y - y1;
        long long dx2 = x - x2, dy2 = y - y2;

        a[i].d1 = dx1 * dx1 + dy1 * dy1;
        a[i].d2 = dx2 * dx2 + dy2 * dy2;
    }

    // 按照到第一套系统的距离平方从小到大排序
    sort(a.begin(), a.end(), [](const Node& p, const Node& q) {
        if (p.d1 != q.d1) return p.d1 < q.d1;
        return p.d2 < q.d2;
    });

    // suf[i] 表示从 i 到末尾的导弹中，到第二套系统距离平方的最大值
    vector<long long> suf(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = max(suf[i + 1], a[i].d2);
    }

    // 所有导弹都由第二套系统拦截
    long long ans = suf[0];

    // 枚举第一套系统的工作半径平方
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && a[j].d1 == a[i].d1) {
            j++;
        }

        // 第一套系统半径平方为 a[i].d1
        // 覆盖 [0, j-1] 的导弹
        // 第二套系统覆盖 [j, n-1] 的导弹
        ans = min(ans, a[i].d1 + suf[j]);

        i = j;
    }

    cout << ans << '\n';

    return 0;
}