题解 P1158 【导弹拦截】

cyw陌浟 · 2017-08-14 15:22:27 · 题解

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100000+1; //数组最大量=导弹数量上限n+1，因为下标0不用 
int x1,y1,x2,y2,n,i,x,y,r2,ans;
//雷达1、2的坐标，导弹数量，每次输入的导弹的坐标，雷达2的半径平方，最小成本 
struct data{int one,two;}d[maxn]; //第i个导弹到两个雷达的距离的平方 
int compare(data a,data b) //比较两个导弹到雷达1的距离平方的大小 
{ 
    if (a.one<=b.one) return 1;
      else return 0;
}
int main()
{
    scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n); //输入雷达坐标和导弹数量
    for(i=1;i<=n;i++) 
    {
        scanf("%d%d",&x,&y); //输入导弹坐标
        d[i].one=(x-x1)*(x-x1)+(y-y1)*(y-y1); //计算导弹到雷达1的距离的平方 
        d[i].two=(x-x2)*(x-x2)+(y-y2)*(y-y2); //计算导弹到雷达2的距离的平方 
       }
    sort(d+1,d+1+n,compare); //快排：按到雷达1的距离从小到大排序
    r2=0; //雷达2不开，其半径平方=0，无导弹由雷达2负责
    ans=d[n].one; //成本假设初值：导弹1~n由雷达1负责，成本等于最大的导弹到雷达1的半径平方
    for(i=n;i>1;i--)
    {
        if(r2<d[i].two) {r2=d[i].two;} //雷达2的半径 
        if(d[i-1].one+r2<ans) //i-1及之前的导弹由雷达1负责，i及之后的导弹由雷达2负责，此时的成本比原来的成本小 
        {ans=d[i-1].one+r2;} //更新最小成本ans 
    }
    printf("%d",ans); //输出答案
    return 0;
}