题解 P1158 【导弹拦截】

kkksx · 2018-08-21 17:35:10 · 题解

using namespace std;
struct daodan
{
    int dis1,dis2;
}d[100005];//每个导弹分别到1,2的距离 
bool cmp(daodan x,daodan y){return x.dis1<y.dis1;}//将离1距离大的导弹放后面 
int main()
{   
    int n,x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin>>x>>y;//导弹的横纵坐标 
        d[i].dis1=(x-x1)*(x-x1)+(y-y1)*(y-y1);//
        d[i].dis2=(x-x2)*(x-x2)+(y-y2)*(y-y2);//到1,2距离 
    }
    sort(d+1,d+n+1,cmp);//排序，将离1大的放后面 
    int r2=0;//2号半径平方用一个变量记录就行，如果小了就更新 
    int ans=d[n].dis1;//全部导弹都用1拦截，即距离=拦截最远的 
    for(int i=n-1;i>=1;--i)//从后面开始一个个的给2拦截 ，1的半径减小 
    {
        if(r2<d[i+1].dis2) r2=d[i+1].dis2;//如果新加入2的那个导弹距离比之前的都大，就更新 
        ans=min(ans,d[i].dis1+r2);//答案为原答案和现在的最小值 
    }
    cout<<ans<<endl;
    return 0;
}