一、题目内容

题目描述

经过11年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。

某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

输入描述

第一行包含4个整数x1,y1,x2,y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x1,y1)、(x2,y2)。
第二行包含1个整数N，表示有N颗导弹。接下来N行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。

输出描述

输出只有一行，包含一个整数，即当天的最小使用代价。

示例1

输入

0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1

输出

30

说明

样例中的导弹拦截系统和导弹所在的位置如图1所示。要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为20和10。

图1

备注：

对于10%的数据，N=1
对于20%的数据，1≤N≤2
对于40%的数据，1≤N≤100
对于70%的数据，1≤N≤1000
对于100%的数据，1≤N≤ 100000，且所有坐标分量的绝对值都不超过1000

二、解题思路

简单贪心，我们可以让第一个雷达包围所有的点，然后不断缩小第一个雷达的半径，每次圆边缘的点都会从圈内出来，我们用第二个雷达去包含它即可。
先将所有点到第一个雷达的距离从大到小排序，依次枚举所有点所在圆的半径，当新点到第二个雷达的距离大于当前半径时，则将半径更新为新的距离。

代码实操：

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int x, y, d;
    bool friend operator < (Node a,Node b) {
        return a.d > b.d;
    }
}s[100010];
 
int dis(int x, int y, int a, int b) {
    return (x - a) * (x - a) + (y - b) * (y - b);
}
 
int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> s[i].x >> s[i].y;
        s[i].d = dis(x1, y1, s[i].x, s[i].y);
    }
     
    sort(s + 1,s + n + 1);
     
    int r1 = s[1].d;
    int r2 = 0;
    int ans = r1;
    for (int i = 2; i <= n+1; i++) {
        r1 = s[i].d;
        r2 = max(r2,dis(x2,y2,s[i-1].x,s[i-1].y));
        ans = min(ans,r1 + r2);
    }
    cout << ans << endl;
    return 0;
}

最后编辑于：2019.11.27 16:57:59