题解 P1158 【导弹拦截】

_•́へ•́╬_ · 2018-09-08 19:41:56 · 题解

下面的dalao讲的够清楚了，不过我预处理出了每个节点的【d1】（与1号系统的距离）和【d2】（与2号系统的距离）

#include<bits/stdc++.h>//懒人专用头文件
#define rpt(n) for(register int ttxyc=0;ttxyc<n;++ttxyc)//宏
using namespace std;
inline int read()//快读
{
    register int X=0,w=0;register char c=getchar();
    for(;c<'0'||c>'9';w|=c=='-',c=getchar());
    for(;c>='0'&&c<='9';X=(X<<3)+(X<<1)+(c^48),c=getchar());
    return w?-X:X;
}
struct xy
{
    int x,y,d1,d2;
}zzz[100000];
int a,b,c,d,n,ans=1<<30,kkk[100001];
inline bool cmp(xy p,xy q)
{
    return p.d1<q.d1;
}
main()
{
    a=read();b=read();c=read();d=read();n=read();//压行好玩
    rpt(n)
    {
        zzz[ttxyc].x=read();zzz[ttxyc].y=read();
        zzz[ttxyc].d1=(a-zzz[ttxyc].x)*(a-zzz[ttxyc].x)+//【d1】
                      (b-zzz[ttxyc].y)*(b-zzz[ttxyc].y);
        zzz[ttxyc].d2=(c-zzz[ttxyc].x)*(c-zzz[ttxyc].x)+//【d2】
                      (d-zzz[ttxyc].y)*(d-zzz[ttxyc].y);
    }
    sort(zzz,zzz+n,cmp);
    kkk[n-1]=zzz[n-1].d2;
    for(register int i=n-2;i>=0;--i)kkk[i]=max(kkk[i+1],zzz[i].d2);//这个数组是写从i开始往后找，离2号系统最远的距离
    ans=kkk[0];
    rpt(n)ans=min(ans,zzz[ttxyc].d1+kkk[ttxyc+1]);
    //                1号系统的代价  2号系统的代价
    printf("%d",ans);//输出
}/**/