P1158 导弹拦截

P1158 导弹拦截

思路：

按每个点到第一个系统的距离排序，然后预处理出每个点及其之后的点到第二个系统的距离的最大值，再循环一遍枚举答案。

 代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;

#define res register int
inline int read()
{
    int x(0),f(1); char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
    while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return f*x;
}
typedef long long LL;
const int N=100000+10;
int n,x1,y1,x2,y2;
int d[N];
struct node{
    int x,y,z;
}s[N];
inline int calc(int a1,int b1,int a2,int b2)
{
    return (a1-a2)*(a1-a2)+(b1-b2)*(b1-b2);
}
bool cmp(node a,node b) {return a.z<b.z;}
int main()
{
    x1=read(); y1=read(); x2=read(); y2=read(); n=read();
    for(res i=1 ; i<=n ; i++)
    {
        s[i].x=read(); s[i].y=read(); 
        s[i].z=calc(x1,y1,s[i].x,s[i].y);    
    }
    sort(s+1,s+n+1,cmp);
    for(res i=n ; i>=1 ; i--)
        d[i]=max(d[i+1],calc(x2,y2,s[i].x,s[i].y)); 
    int ans(d[1]);
    for(res i=1 ; i<=n ; i++)
    {
        int tmp(s[i].z); tmp+=d[i+1];
        ans=min(ans,tmp);
    }
    printf("%d\n",ans);
    return 0;
}