题解 | 导弹拦截-NOIP2010普及组复赛
导弹拦截
https://ac.nowcoder.com/acm/contest/238/B
算法：枚举,排序
复杂度：)
解题思路：
先用第一个雷达包围所有点，然后不断缩小第一个雷达的半径，每次圆边缘的点会从圈内出来，我们用第二个雷达去包含它 即可。
枚举半径的方法：先将所有点按到第一个雷达的距离从大到小排序，依次枚举所有点所在的圆的半径即可。
用第二个雷达去包含新点的方法：如果新点到第二个雷达的距离大于当前半径长度，则将半径更新成新的距离。
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;
} 
美的集团公司福利 814人发布