P1158 导弹拦截

算法

142

一言准备中...

导弹拦截

洛谷原题：P1158 导弹拦截

有两套导弹拦截系统，位置分别为：

$$ (x_1,y_1) $$

和：

$$ (x_2,y_2) $$

现在有若干枚导弹，每枚导弹的位置为：

$$ (x_i,y_i) $$

两套系统都可以设置一个拦截半径，只要一枚导弹落在其中至少一套系统的覆盖范围内，就算能够被拦截。

要求最小化：

$$ r_1^2+r_2^2 $$

思路

对于每一枚导弹，可以分别计算它到两套系统的距离平方。

记：

$$ d_{i1}=(x_i-x_1)^2+(y_i-y_1)^2 $$

$$ d_{i2}=(x_i-x_2)^2+(y_i-y_2)^2 $$

因为题目最终要求的也是半径平方之和，所以整个过程中没有必要开根号，直接比较距离平方即可。

对每枚导弹保存：

dis1
dis2

其中：

dis1 = 到第一套系统的距离平方
dis2 = 到第二套系统的距离平方

为什么可以排序

先按照：

dis1

从小到大排序。

假设排序以后为：

m[0], m[1], m[2], ... , m[N-1]

如果决定第一套系统负责前面的若干枚导弹，那么第一套系统所需要的最小半径平方，就是这些导弹中最大的 dis1。

因为已经按照 dis1 排序，所以假设第一套系统负责：

m[0] ~ m[i]

那么：

$$ r_1^2=m[i].dis1 $$

剩下的：

m[i+1] ~ m[N-1]

全部交给第二套系统。

第二套系统需要覆盖这些导弹，所以：

$$ r_2^2= \max_{j=i+1}^{N-1}m[j].dis2 $$

于是当前这个分界点的答案就是：

$$ m[i].dis1+ \max_{j=i+1}^{N-1}m[j].dis2 $$

问题就变成：

枚举第一套系统负责到哪一枚导弹为止。

为什么只需要枚举这个分界点

假设第一套系统的半径已经确定为：

$$ r_1^2=m[i].dis1 $$

因为数组已经按照 dis1 排序，所以：

m[0]
m[1]
...
m[i]

全部都在第一套系统覆盖范围内。

因此这些导弹没有必要再强制交给第二套系统。

真正需要第二套系统负责的，只剩：

m[i+1]
...
m[N-1]

第二套系统的半径就由这些导弹中最大的 dis2 决定。

所以枚举：

i = N-1, N-2, ... , 0

就等于枚举第一套系统负责的导弹数量。

从后往前维护第二套系统半径

如果每枚举一个 i，都重新扫描：

m[i+1] ~ m[N-1]

寻找最大的 dis2，就会产生很多重复计算。

所以可以从后往前枚举，同时维护：

int r2 = 0;

每次把刚刚进入第二套系统负责范围的导弹加入：

if (r2 < m[i + 1].dis2)
    r2 = m[i + 1].dis2;

这样 r2 始终表示当前第二套系统需要的最大半径平方。

然后计算：

m[i].dis1 + r2

取所有情况中的最小值。

例如排序以后：

m[0]
m[1]
m[2]
m[3]
m[4]

可以依次考虑：

系统1：m[0] ~ m[4]
系统2：空

然后：

系统1：m[0] ~ m[3]
系统2：m[4]

继续：

系统1：m[0] ~ m[2]
系统2：m[3] ~ m[4]

再继续：

系统1：m[0] ~ m[1]
系统2：m[2] ~ m[4]

最后：

系统1：m[0]
系统2：m[1] ~ m[4]

不断比较：

$$ r_1^2+r_2^2 $$

的最小值即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 10;
int x1, y1, x2, y2, N;

struct missile
{
    int dis1;
    int dis2;
}m[maxn];

bool cmp(missile a, missile b)
{
    return a.dis1 < b.dis1;
}

int main()
{
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        m[i].dis1 = (x - x1) * (x - x1) + (y - y1) * (y - y1);
        m[i].dis2 = (x - x2) * (x - x2) + (y - y2) * (y - y2);
    }

    sort(m, m + N, cmp);

    int res = m[N - 1].dis1;
    int r2 = 0;

    for (int i = N - 1; i >= 0; i--)
    {
        if (r2 < m[i + 1].dis2)
            r2 = m[i + 1].dis2;

        res = min(res, m[i].dis1 + r2);
    }

    cout << res << endl;

    return 0;
}

复杂度

首先需要对 N 枚导弹按照 dis1 排序：

$$ O(N\log N) $$

之后从后向前扫描一次：

$$ O(N) $$

所以总时间复杂度为：

$$ O(N\log N) $$

主要空间用于保存所有导弹的两个距离，因此空间复杂度为：

$$ O(N) $$

总结

这题比较关键的地方不是距离公式，而是把二维的“两个圆怎么分配导弹”转成一个可以枚举的分界点。

先按照第一套系统的距离排序：

dis1 从小到大

然后枚举：

第一套系统负责一个前缀
第二套系统负责剩下的后缀

对于每一个分界点：

$$ r_1^2=m[i].dis1 $$

而：

$$ r_2^2= \max_{j=i+1}^{N-1}m[j].dis2 $$

从后向前枚举时，再顺便维护第二部分的最大 dis2，就不需要重复扫描。

所以最后就是：

计算两套距离
        ↓
按照 dis1 排序
        ↓
从后向前枚举分界点
        ↓
维护后缀最大的 dis2
        ↓
更新 r1² + r2²