2010年T3 导弹拦截

· · 题解

题目描述

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

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

输入格式

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

输出格式

一个整数，即当天的最小使用代价。

思路：将所有导弹到a，b两雷达的距离的平方存入a，b数组，排序。用xh表示雷达的编号，枚举前i个被a导弹拦截，其余给b。最后取值再与最小值进行比较。

#include<bits/stdc++.h>
using namespace std;
int x,y,x2,y2,n,ans,c[1000001],minn=1e9;
struct cmp{
    int xh,zh;
}a[1000001],b[1000001];
bool f(cmp x,cmp y){
    return x.zh<y.zh;
}
int main(){
    cin>>x>>y>>x2>>y2;
    cin>>n;
    int a1,b1;
    for(int i=1;i<=n;i++){
        cin>>a1>>b1;
        a[i].zh=pow(a1-x,2)+pow(b1-y,2);
        b[i].zh=pow(a1-x2,2)+pow(b1-y2,2);
        a[i].xh=i;
        b[i].xh=i;
    }
    sort(a+1,a+n+1,f);
    sort(b+1,b+n+1,f);  
    int k=n;
    for(int i=1;i<=n;i++){
        c[a[i].xh]=1;
        while(c[b[k].xh]==1){
            k--;
        }
        if(a[i].zh+b[k].zh<minn){
            minn=a[i].zh+b[k].zh;
        }
    }
    cout<<minn;
}