代码

洛谷原题-导弹拦截

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
int x1, y1, x2, y2, N;

struct missile
{
    int dis1;
    int dis2;
}m[maxn];

bool cmp(missile a, missile b)
{
    return a.dis1 < b.dis1;
}

int main()
{
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        m[i].dis1 = (x - x1) * (x - x1) + (y - y1) * (y - y1);
        m[i].dis2 = (x - x2) * (x - x2) + (y - y2) * (y - y2);
    }

    sort(m, m + N, cmp);

    int res = m[N - 1].dis1;
    int r2 = 0;

    for (int i = N - 1; i >= 0; i--)
    {
        if (r2 < m[i + 1].dis2)
            r2 = m[i + 1].dis2;

        res = min(res, m[i].dis1 + r2);
    }

    cout << res << endl;

    return 0;
}

2024年2月 补充

整理代码的时候重新看了一遍，发现这里其实漏掉了一种情况。

原程序先令：

res = m[N - 1].dis1;

这相当于考虑了所有导弹全部由第一套系统拦截、第二套系统半径为 0 的情况。之后再不断缩小第一套系统负责的范围，把后面的导弹交给第二套系统。

但循环最终只枚举到第一套系统至少还负责一颗导弹，并没有继续走到第一套系统半径为 0、全部导弹都由第二套系统负责的情况。也就是说，当第二套系统的位置明显更有利时，原来的代码可能错过真正的最优解。

修正其实很简单，在第二套系统已经统计完所有导弹以后，再比较一次即可：

res = min(res, r2);

当然，如果重新写这道题，我大概会把整个枚举边界写得更明确一点。不过上面的代码还是保留高中时原来的版本，不改了。