题目描述

经过 11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。

当工作半径为 0 时，则能够拦截与它位置恰好相同的导弹。

但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。

而当天的使用代价，就是所有系统工作半径的平方和。 

某天，雷达捕捉到敌国的导弹来袭。

由于该系统尚处于试验阶段，所以只有两套系统投入工作。

如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

输入格式

第一行包含 4 个整数 x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为 (x1,y1)、(x2,y2)。

第二行包含 1 个整数 N，表示有 N 颗导弹。

接下来 N 行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x,y)，不同导弹的坐标可能相同。

输出格式

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

数据范围

1 ≤ N ≤ 105 , 所有坐标分量的绝对值都不超过 1000 。

输入样例：

(据点1坐标)0 0 (据点2坐标)6 0
(导弹个数)5
(导弹1) -4 -2  
(导弹2) -2 3   
(导弹3)  4 0   
(导弹4)  6 -2  
(导弹5)  9 1   

输出样例：

30

思路

                总思想：取每个据点负责的所有导弹中距离最远的作为该据点的半径

• 分别计算每个导弹距离据点1，2的距离(半径的平方)，放在类型为pair的数组中，数组中first是距离据点1的距离，second是距离据点2的距离。
• 对pair数组排序，默认按距离据点1的距离升序排列
• 从最远距离(i == n)开始枚举，每个据点取最远距离作为半径并计算代价，1号据点负责i个导弹，2号据点负责剩余 n - i 个导弹

具体过程如下

r1 : 距离据点 1 最远距离的导弹 ， r2 ：距离据点 2 最远的导弹 ， res：代价
从离 据点1 最远的距离开始枚举
i == 5 , r1 = 82 , r2 = 0 , res = 82 ; (据点 1 拦截 5 个导弹 ， 据点 2 拦截 0 个导弹)
i == 4 , r1 = 40 , r2 = 10 , res = 50 ; (据点 1 拦截 4 个导弹 ， 据点 2 拦截 1 个导弹) 
i == 3 , r1 = 20 , r2 = 10 , res = 30 ; (据点 1 拦截 3 个导弹 ， 据点 2 拦截 2 个导弹)
i == 2 , r1 = 16 , r2 = 104 , res = 120 ; (据点 1 拦截 2 个导弹 ， 据点 2 拦截 3 个导弹)
i == 1 , r1 = 13 , r2 = 104 , res = 117 ; (据点 1 拦截 1 个导弹 ， 据点 2 拦截 4 个导弹)
i == 0 , r1 = 0 , r2 = 104 , res = 104 ; (据点 1 拦截 0 个导弹 ， 据点 2 拦截 5 个导弹)

所以最小代价是 ： res = 30 (据点 1 拦截 3 个导弹 ， 据点 2 拦截 2 个导弹)

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int , int > PII;

const int N = 1e5+10;

PII a[N];
int n ;

int main()
{
    int x1 , y1 , x2 , y2 ;
    cin >> x1 >> y1 >> x2 >> y2 >> n;

    for (int i = 1 ; i <= n ; i ++)
    {
        int x , y ;
        cin >> x >> y ;
        int d1 = (x - x1) * (x - x1) + (y - y1) * (y - y1);
        int d2 = (x - x2) * (x - x2) + (y - y2) * (y - y2);
        a[i] = {d1 , d2};
    }

    sort (a + 1 , a + 1 + n); // 按导弹据(x1,y1)半径升序排序

    int r1 = 0 , r2 = 0 , res = 0x3f3f3f3f; 
    for (int i = n ; i >= 0 ; i --) // i 表示 (x1,y1)据点包含的导弹数 从n开始 
    {
        if ( i == 0 ) r1 = 0; // i 为 0 ， 则 没有导弹为据点1负责 ， 全部为据点2负责 
        else r1 = a[i].first; // i只要不是0 ，因为已经升序排列 ， 所以r1 只需要为 i个导弹内最远的 即a[i].first

        if ( i == n ) r2 = 0; 
        else r2 = max (r2 , a[i + 1].second); // r2为据点2负责的导弹 即 据点1负责的i个导弹外剩余的导弹内最远的那一个导弹，每次用max(当前导弹据r2据点距离，i+1个导弹剩余的最远导弹距离)

        res = min ( res , r1 + r2 );  //成本取最小
    }

    cout << res << endl;
}