算法

(枚举,排序) $O(nlogn)$

先用第一个雷达包围所有点，然后不断缩小第一个雷达的半径，每次圆边缘的点会从圈内出来，我们用第二个雷达去包含它 即可。

枚举半径的方法：先将所有点按到第一个雷达的距离从大到小排序，依次枚举所有点所在的圆的半径即可。

用第二个雷达去包含新点的方法：如果新点到第二个雷达的距离大于当前半径长度，则将半径更新成新的距离。

时间复杂度

排序是算法瓶颈，因此总时间复杂度是 $O(nlogn)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a1, b1, a2, b2;

struct Point
{
    int x, y;
    int d;
    bool operator< (const Point &W)const
    {
        return d < W.d;
    }
}point[N];


int get_dist(int x1, int y1, int x2, int y2)
{
    int dx = x1 - x2;
    int dy = y1 - y2;
    return dx * dx + dy * dy;
}


int main()
{
    scanf("%d%d%d%d", &a1, &b1, &a2, &b2);
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        point[i] = {x, y, get_dist(x, y, a1, b1)};
    }

    sort(point, point + n);
    reverse(point, point + n);

    int res = point[0].d, r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        r = max(r, get_dist(point[i - 1].x, point[i - 1].y, a2, b2));
        res = min(res, point[i].d + r);
    }

    printf("%d\n", res);
    return 0;
}