题前吐槽

这道题没有题解？

说难呢？这道题就是把枚举优化一下下。说简单呢？又不会……

这道题的样例图缺失了，我来补一下：

题解

这道题我们要理解一点，就是一个导弹不被 $1$ 号拦截就是被 $2$ 号拦截了。

那我们可以让 $1$ 号拦截一部分导弹，剩下的都给 $2$ 号。所以我们可以枚举 $1$ 号帮忙拦截了哪些导弹，然后 $1$ 号的射程半径就是其中最远的一个距离 $1$ 号的距离；其他的留给 $2$ 号，$2$ 号的射程计算类似。

可是这样的枚举太慢了，会超时。我们需要线性枚举。

我们观察一下，发现 $1$ 号在拦截较远的导弹时把近处的全部拦截了，所以我们只需要枚举 $1$ 号打到哪一个导弹就可以了，距离更近的也归 $1$ 号，没有被 $1$ 号覆盖的都给 $2$ 号。

这样为了方便计算，我们可以把导弹写成一个结构体，包含到 $1$ 号和 $2$ 号的距离。然后我们根据到 $1$ 号的距离递增排序，枚举 $1$ 号打到哪一个。

我们还是直接看完整代码吧：

#include <bits/stdc++.h>
// Linux下的变量名占用问题，可以使用#define调节
#define x1 _____x1
#define x2 _____x2
#define y1 _____y1
#define y2 _____y2
using namespace std;
int N, x, y;
int x1, y1, x2, y2;
int r1, r2, ans = 1e9; // AC与WA就在1e9与0之间……（作者血的教训
struct point
{
    int id, x, y, dis1, dis2;
    // id 编号（没啥用
    // x, y 坐标
    // dis1, dis2 到俩炮台的距离
} p[100005];
bool cmp(point a, point b) // 结构体排序的cmp
{
    return a.dis1 < b.dis1; // dis1递增
}
int dis(int x, int y, point b) // 计算一个点和一个点之间的距离的平方（因为答案也是平方和，为避免小数这里也按平方算
{
    int f1 = abs(x - b.x);
    int f2 = abs(y - b.y);
    return f1 * f1 + f2 * f2;
}
int main()
{
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &N);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d%d", &x, &y);
        p[i].id = i;
        p[i].x = x;
        p[i].y = y;
        p[i].dis1 = dis(x1, y1, p[i]); // 计算距离
        p[i].dis2 = dis(x2, y2, p[i]);
    }
    sort(p + 1, p + N + 1, cmp); // 排序
    for (int i = N; i >= 0; i--) // 这里枚举两个炮台负责的边界处
    {
        r1 = p[i].dis1; // 1号的半径很好求
        // 2号半径不能直接p[i + 1].dis2，因为dis2不一定递增。
        if (r2 < p[i + 1].dis2) r2 = p[i + 1].dis2; // 只有在r2不够时才增加，这样也是最大值
        ans = min(ans, r1 + r2); // 最小值
    }
    printf("%d\n", ans);
    return 0;
}

$AC$ $Code$

#include <bits/stdc++.h>
#define x1 _____x1
#define x2 _____x2
#define y1 _____y1
#define y2 _____y2
using namespace std;
int N, x, y;
int x1, y1, x2, y2;
int r1, r2, ans = 1e9;
struct point
{
    int id, x, y, dis1, dis2;
} p[100005];
bool cmp(point a, point b)
{
    return a.dis1 < b.dis1;
}
int dis(int x, int y, point b)
{
    int f1 = abs(x - b.x);
    int f2 = abs(y - b.y);
    return f1 * f1 + f2 * f2;
}
int main()
{
    scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &N);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d%d", &x, &y);
        p[i].id = i;
        p[i].x = x;
        p[i].y = y;
        p[i].dis1 = dis(x1, y1, p[i]);
        p[i].dis2 = dis(x2, y2, p[i]);
    }
    sort(p + 1, p + N + 1, cmp);
    for (int i = N; i >= 0; i--)
    {
        r1 = p[i].dis1;
        if (r2 < p[i + 1].dis2) r2 = p[i + 1].dis2;
        ans = min(ans, r1 + r2);
    }
    printf("%d\n", ans);
    return 0;
}