题解 P1158 【导弹拦截】

· · 题解

这一道题是智障能推荐给我的，（当时以为是那道DP，因为也是NOIP的），10分钟过去之后，发现自己只能想出N^2的算法，于是（点开题解），看到大佬们的题解，总算把这道题弄懂了，可很多大佬的讲解比较粗略，（像我这种蒟蒻只有看代码才能看懂），所以这里打算写一遍稍微详细一点的题解。

预备知识：贪心，后缀数组（后缀最大值）。

首先有一个很明显的道理：当两个系统的最远距离都和某个（可能是不同的点）重合时，答案比不重合更优。

如下图，上面的显然比下面的更优

接下来就是考虑系统的边缘落在哪个点上的问题，观察用脑子想想容易得到，若dis_i>dis_j(dis_i表示i号导弹到某个系统的距离)，则当系统能够覆盖到点i时，必定能够覆盖到点j（圆的半径都相等）

由此，我们想到把导弹的距离进行排序，按照每颗导弹距离一号系统的距离进行排序，排完序以后，我们可以近似的把每颗炮弹看成在一条线上。且都在系统一的某一侧，如下图 （其中橙色的点表示原炮弹所在位置，红色的表示将炮弹看成在一条线上的位置，绿色的表示系统）

于是，题目就变成了一个寻找分割位置的问题，我们可以枚举i∈[1,N]，即把距离系统1距离排序后的前i颗导弹交给系统1解决，剩余的N-i颗导弹交给系统2去解决。系统一的半径当然就是dis1_i，那系统二的半径则可以通过后缀最大值数组处理出来。

此处有一个小技巧，关注到答案要求的是半径的平方和，又因为两个系统所用的代价只与其的半径有关，而与其内部的导弹距离无关，故我们可以在计算距离时，直接用平方进行计算，从而避免{\sqrt{dis}}^2带来的精度问题。

时间复杂度：处理距离Θ(N),快速排序O(NlogN)，枚举分割点Θ(N)，总体复杂度Ω(NlogN)

以下是代码部分

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define rap(a,b,c) for(int a=(b);a>=(c);a--)
#define pow2(x) ((x)*(x))
//带参数的宏定义最好给每个数字参数套上括号哦！
using namespace std;
const int MAXN=1e5+10;
int read()
{
    int x=0,f=0;
    char ch=0;
    while(!isdigit(ch))f|=(ch=='-'),ch=getchar();
    while(isdigit(ch))(x*=10)+=(ch^48),ch=getchar();
    return f?-x:x;
}
//快读
struct Node
{
    int dis1;
    int dis2;
    int x,y;
    bool operator<(const Node &rhs)const
    {
        return dis1<rhs.dis1;
    }
} node[MAXN];
//定义存储导弹信息的结构体，并重载运算符，按照距离一号系统的距离进行排序
int n;
int X1,Y1,X2,Y2;
//x1,y1,_x1,_y1属于系统保留的关键字，在Windows中可能不会报错，但在Linux中是肯定会CE的！
int ans=INT_MAX;

int main()
{
    X1=read(),Y1=read();
    X2=read(),Y2=read();
    n=read();

    rep(i,1,n)
    node[i].x=read(),node[i].y=read();
   //读入部分

    rep(i,1,n)
    {
        node[i].dis1=pow2(X1-node[i].x)+pow2(Y1-node[i].y);
        node[i].dis2=pow2(X2-node[i].x)+pow2(Y2-node[i].y);
    }
   //处理出导弹到每个系统的距离，为何不使用sqrt的原因上文已经阐述过了

    sort(node+1,node+n+1);
   //按照导弹到一号系统的距离排序

    rap(i,n-1,1)
    node[i].dis2=max(node[i].dis2,node[i+1].dis2);
   //处理出后缀最大值

    rep(i,1,n)
    ans=min(ans,node[i].dis1+node[i+1].dis2);
   //枚举分割点，把前i个交给一号系统，后面N-i个交给二号系统，由于我们在处理时就使用平方进行计算，故这里不需要在平方

    printf("%d\n",ans);
    return 0;//O=w=O
}