思路与算法

按到第一系统的距离平方排序，枚举已覆盖前缀，剩余后缀到第二系统的最大距离给第二半径；区别于最长非上升导弹拦截题。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

固定第一半径后，所有未覆盖点只能交给第二系统，第二半径平方的最小值就是它们到第二系统的最大平方距离。最优第一半径可收缩到0或某颗导弹距离，因此排序枚举所有前缀和0完整覆盖最优选择。

复杂度

O(n log n)时间、O(n)距离存储，后向扫描线性。

易错点

必须包含一个系统半径0的情形；重复距离可以在同一值全部纳入，扫描中的中间切分只会高估同值最终切分，不会产生低于可行最优的结果。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int n;
    cin >> n;
    vector<pair<long long, long long>> a(n);
    for (auto &v : a) {
        long long x, y;
        cin >> x >> y;
        v = {(x - x1) * (x - x1) + (y - y1) * (y - y1), (x - x2) * (x - x2) + (y - y2) * (y - y2)};
    }
    sort(a.begin(), a.end());
    long long s = 0, ans = LLONG_MAX;
    for (int i = n - 1; i >= 0; i--) {
        ans = min(ans, a[i].first + s);
        s = max(s, a[i].second);
    }
    ans = min(ans, s);
    cout << ans << "\n";
}