题解 P1158 【导弹拦截】

Lin1043 · 2017-08-19 22:14:40 · 题解

这道题是贪心，对于每一个每个点到A和B的距离都是确定的，所以我们可以只考虑一个A所要去覆盖的点，A不能覆盖到的点显然就要让B来覆盖，

设ra_i,rb_i为第i个点分别到A和B的距离。

在对ra_i进行排序之后，可以得到一个

的序列，可以证明当i<j的时候取j显然会包括i，然后我们就可以求解了。同时还有一点就是循环从后往前搜是更优的，因为rb_i是无序的，从后往前更新一下B的最大半径省去了从前往后搜的很多细节问题。

#include <cstdio>
#include <cstdlib>
#include <ctype.h>
#include <algorithm>

#define ll long long
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b

template<typename T>
inline T read(){
    T f=0,x=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')x=-1;c=getchar();}
    while(isdigit(c))f=f*10+c-'0',c=getchar();
    return f*x;
}

const int maxn=100005;

int Ax,Ay,Bx,By;
int n,x,y;

struct Node{
    int A,B;

    bool operator <(const Node &b)const{
        return A<b.A;
    }
}P[maxn];

int dist(int A,int B,int C,int D){
    return (A-C)*(A-C)+(B-D)*(B-D);
}

int main(){
    Ax=read<int>();
    Ay=read<int>();
    Bx=read<int>();
    By=read<int>();

    n=read<int>();

    for(int i=1;i<=n;i++){
        x=read<int>();
        y=read<int>();

        P[i].A=dist(Ax,Ay,x,y);
        P[i].B=dist(Bx,By,x,y);
    }

    std::sort(P+1,P+1+n);

    int ans=1<<30,r2=0;    
    for(int i=n;i>=1;i--){
        r2=max(r2,P[i+1].B);
        ans=min(ans,r2+P[i].A);
    }
    printf("%d\n",ans);    
    return 0;
}