P4717 导弹拦截（基础）

解题思路

题目在问什么：有两套导弹拦截系统，坐标分别是 $(x_1,y_1)$ 和 $(x_2,y_2)$。每套系统当天只能设定一次工作半径，当天的代价就是两套系统半径平方之和。现在必须把所有的导弹都拦住，求这一天的最小代价。

第一步，想清楚一个关键性质。 只要确定了"系统1负责拦哪些导弹"，系统1的半径就必须至少等于这些导弹里离它最远的那一颗的距离；剩下的导弹交给系统2，系统2的半径就等于剩下导弹里离它最远的那一颗的距离。所以我们只需要决定"把哪些导弹分给系统1"，答案就唯一确定了。

第二步，决定怎么分。 把所有导弹按"到系统1的距离"从小到大排序。这样不管系统1的半径定多大，它能拦下的永远是排序后前面的若干颗（前缀）：因为半径连远处那颗都够得着，那更近的每一颗自然也都够得着。剩下没拦住的（后缀）全部交给系统2。这条"前缀分法"让枚举变得特别简单。

第三步，提前算好后缀。 排好序后，记 maxD2[i] 表示"从第 i 颗到最后一颗导弹里，到系统2距离平方的最大值"。这样当系统1负责前 i 颗时，系统2要拦下剩下那一堆，它的半径平方就是 maxD2[i+1]，不需要每次重新扫一遍，一次预处理就够。

第四步，枚举每一种分法取最小。 系统1负责前 0 颗（也就是全部交给系统2）、前 1 颗、前 2 颗……一直到前 n 颗，对每一种都算出 to1 + maxD2[i+1]，取其中最小的就是答案。注意"前 0 颗"对应系统1的半径是 0，这一种分法最容易漏，一定要算进去。

细节提醒：坐标可以很大，距离平方之后可能超过 int 能表示的范围，所以距离和代价都要用 long long 存储。

参考代码

// 导弹拦截：两套拦截系统覆盖所有导弹，求两套半径平方和的最小值
#include <iostream>
#include <algorithm>
using namespace std;

// 每颗导弹：存它到两套系统的平方距离
struct Missile {
    long long to1; // 到系统1的距离平方
    long long to2; // 到系统2的距离平方
};

Missile a[100005];        // a 数组存下所有导弹
long long maxD2[100005];  // maxD2[i]：从第 i 颗到最后一颗里，到系统2距离平方的最大值

// 按"到系统1的距离"从小到大排序
bool cmp(Missile x, Missile y) {
    return x.to1 < y.to1;
}

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        a[i].to1 = (x - x1) * (x - x1) + (y - y1) * (y - y1); // 到系统1的距离平方
        a[i].to2 = (x - x2) * (x - x2) + (y - y2) * (y - y2); // 到系统2的距离平方
    }
    sort(a, a + n, cmp);  // 把导弹按到系统1的距离从小到大排
    maxD2[n] = 0;         // 最后一颗导弹的后面是空的
    for (int i = n - 1; i >= 0; i--) {
        maxD2[i] = max(maxD2[i + 1], a[i].to2);  // 从后往前记下后缀里的最大距离
    }
    long long ans = maxD2[0];  // 情况一：全部交给系统2，系统1的半径是0
    for (int i = 0; i < n; i++) {
        // 情况二：系统1管前 i+1 颗（半径 a[i].to1），系统2管剩下的（半径 maxD2[i+1]）
        long long now = a[i].to1 + maxD2[i + 1];
        if (now < ans) ans = now;
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

排序用 sort()，时间复杂度 O(n log n)，n 是导弹数量（最大 100000）。排完序之后，后缀数组的预处理是一遍倒着扫，O(n)；枚举每一种分法也是一遍正着扫，O(n)。所以总时间复杂度是 O(n log n)，跑起来非常快。

空间方面，存了 n 颗导弹的结构体数组（每个含两个 long long）和一个长度为 n+1 的后缀数组，空间复杂度 O(n)。