题解 P1158 【导弹拦截】

· · 题解

难度，还可以吧，想出来了就不难了。。。

关键是贪心的思路与后缀和数组，底下代码里写得很详细

附：这是我第一次写题解。。。

/* AKBOY原创

先按照每个顶点到拦截器1的距离排序

(后面的下标按排过序后的为准)

枚举拦截器1的范围 拦截器2就确定了

(边缘必定覆盖一个顶点)

[用后缀和数组 来计算剩余的顶点中与

拦截器2最远的一个 (1~i由于距离都小于

或等于i到拦截器1的距离,必已被拦截器1

覆盖,此时算出i~n中离拦截器2最远的一

个就是拦截器2的半径。。。。。。) ]

由于计算的是平方和,就不需要+sqrt了,

免得麻烦得要死。。。。。。。。。。

*/

#include<cstdio>
#define N 100233
#include<algorithm>
using namespace std;
int n,ans,last[N];
struct Node
{
    int x,y;
}t1,t2,s[N];
inline int Squ(int v);
inline int Dist(Node u,Node v);
bool Cmp(Node p,Node q)
{
    return Dist(t1,p)<Dist(t1,q);
}
int main(void)
{
    freopen("P1158.in","r",stdin);
    freopen("P1158.out","w",stdout);
    scanf("%d%d%d%d",&t1.x,&t1.y,&t2.x,&t2.y);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&s[i].x,&s[i].y);
    sort(s+1,s+1+n,Cmp);
    for(int i=n;i>=1;--i)/*后缀和数组的应用,计算第**i~n**个*/
        last[i]=max(last[i+1],Dist(t2,s[i]));
    ans=0x7fffffff;
    for(int i=1;i<=n;++i)
        ans=min(ans,Dist(t1,s[i])+last[i+1]);
    printf("%d\n",ans);
    return 0;
}
inline int Squ(int v)
{
    return v*v;
}
inline int Dist(Node u,Node v)
{
    return Squ(u.x-v.x)+Squ(u.y-v.y);
}