P1158 导弹拦截

TEoS · 2018-10-26 13:44:11 · 题解

前面有些大佬好像讲得太深奥了，作为蒟蒻我完全看不懂啊，于是我还是以一枚蒟蒻的角度来讲一下吧

思路：

所有的导弹，不是被1号系统拦截就是被2号系统拦截，所以将导弹分成两部分（即被1号系统拦截的部分和被2号系统拦截的部分）进行枚举答案。

因为根据题意，每个系统的半径即为该系统拦截的导弹中距离系统坐标最远的导弹的距离，所以不妨先算出每个导弹距离1号系统的距离，然后以距1号系统的距离进行升序排序。然后从距离1号系统最远的那枚导弹开始，计算出比它距离1号系统的距离远的所有导弹中距离2号系统的距离最远的那个距离（即以它前一枚导弹为1号系统所拦截的最远的导弹时，2号系统的半径），预处理结束后直接进行枚举答案，枚举1号系统所拦截的最远的导弹，然后输出最小的答案即可。 为了方便代码中所有距离直接用它的平方进行比较

接下来是代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int x11,y11,x22,y22,n,minn=4000010;
struct DI
{
    int d1,d2,i;//d1、d2分别为于1、2号系统的距离，i为该导弹的初始编号
}di[1000010];//导弹的信息
bool cmp(DI a,DI b)
{
    return a.d1<b.d1;
}//不会写重载运算符，只能这样写了，排序比较
int main()
{
    cin>>x11>>y11>>x22>>y22>>n;
    int x[n+5],y[n+5];//存储每枚导弹的坐标
    memset(di,0,sizeof(di));//初始化
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        di[i].d1=pow(x[i]-x11,2)+pow(y[i]-y11,2);//计算该枚导弹与1号系统的距离
        di[i].i=i;//存储该枚导弹的初始编号
    }
    sort(di+1,di+n+1,cmp);
    for(int i=n;i>0;i--)
    {
        int a;
        a=pow(x[di[i].i]-x22,2)+pow(y[di[i].i]-y22,2);//计算该枚导弹与2号系统的距离
        di[i].d2=max(a,di[i+1].d2);//比较，若比后面所有导弹的距离都大，则替换
    }
    for(int i=0;i<=n;i++)
    {
        int a;
        a=di[i].d1+di[i+1].d2;//计算以该枚导弹为1号系统拦截的最远导弹所需的代价
        minn=min(a,minn);
    }//枚举答案，取最小值
    cout<<minn;//输出
    return 0;
}

变量名比较土请见谅

这估计是最朴素的一篇代码了