NekoNowcoder

Appearance

赛跑 - 题解 ​

标签与难度 ​

标签: 计算几何, 曼哈顿距离, 切比雪夫距离, 坐标变换, 思维题, 最值问题 难度: 1600

题目大意喵~ ​

哈喵~！各位算法大师们好呀！今天本喵要带大家来解决一道有趣的几何问题，喵~

是这样的，有两个可爱的小伙伴，小 L 和小 R，他们都站在二维平面的原点 (0,0)(0,0)。他们发现自己有了超能力，可以在一秒内移动到一个指定的位置！

  • 小 L 有 nn 种移动选择，每种选择对应一个速度向量 (xL,yL)(x_L, y_L)，也就是说他一秒后可以到达 (xL,yL)(x_L, y_L)。
  • 小 R 也有 mm 种移动选择，每种选择对应一个速度向量 (xR,yR)(x_R, y_R)，一秒后可以到达 (xR,yR)(x_R, y_R)。

他们想知道，如果小 L 和小 R 各自选择一种移动方式，一秒后他们之间能达到的最大曼哈顿距离是多少呢？

напомню (Reminder) 一下，点 (x1,y1)(x_1, y_1) 和 (x2,y2)(x_2, y_2) 之间的曼哈顿距离是 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2| 哦！

解题思路分析 ​

这道题的目标非常明确：最大化小 L 和小 R 之间的曼哈顿距离。让我们先把目标函数写下来，喵~

假设小 L 选择的终点是 PL=(xL,yL)P_L = (x_L, y_L)，小 R 选择的终点是 PR=(xR,yR)P_R = (x_R, y_R)。我们要最大化的就是这个式子：

D=∣xL−xR∣+∣yL−yR∣D = |x_L - x_R| + |y_L - y_R|

这个式子里有绝对值，看起来就让人头大，喵呜... 如果要暴力枚举小 L 的 nn 种选择和小 R 的 mm 种选择，那复杂度就是 O(nm)O(nm)，当 nn 和 mm 很大的时候，肯定会超时的说。我们得想个更聪明的办法！

处理曼哈顿距离问题，有一个非常经典的技巧，那就是坐标变换！就像猫猫我换个角度看毛线球，问题可能就变简单了呢！我们来尝试一下旋转坐标系45度。

具体来说，我们定义一组新的坐标 (u,v)(u, v)：

{u=x+yv=x−y\begin{cases} u = x + y \\ v = x - y \end{cases}

这个变换也被称为曼哈顿距离与切比雪夫距离的转换。

现在，我们来看看原来的曼哈顿距离公式在新的坐标系下会变成什么样。 我们知道一个性质：对于任意实数 aa 和 bb，有 ∣a∣+∣b∣=max⁡(a+b,a−b,−a+b,−a−b)|a| + |b| = \max(a+b, a-b, -a+b, -a-b)。 让 a=xL−xRa = x_L - x_R，b=yL−yRb = y_L - y_R。那么距离 DD 就是：

D=max⁡((xL−xR)+(yL−yR),(xL−xR)−(yL−yR),… )D = \max( (x_L - x_R) + (y_L - y_R), \quad (x_L - x_R) - (y_L - y_R), \quad \dots )

让我们重新组合一下括号里的项：

  1. (xL−xR)+(yL−yR)=(xL+yL)−(xR+yR)=uL−uR(x_L - x_R) + (y_L - y_R) = (x_L + y_L) - (x_R + y_R) = u_L - u_R
  2. (xL−xR)−(yL−yR)=(xL−yL)−(xR−yR)=vL−vR(x_L - x_R) - (y_L - y_R) = (x_L - y_L) - (x_R - y_R) = v_L - v_R

另外两个表达式只是上面两个的相反数，所以我们可以把它们合并成绝对值的形式！

D=max⁡(∣uL−uR∣,∣vL−vR∣)D = \max(|u_L - u_R|, |v_L - v_R|)

哇！看呐！我们成功地把一个麻烦的“和”式距离（曼哈顿距离）变成了一个简单的“最大值”式距离（切比雪夫距离）。在新的 (u,v)(u,v) 坐标系中，两点间的距离是它们在各个坐标轴上差值的最大值。

现在我们的目标变成了最大化 max⁡(∣uL−uR∣,∣vL−vR∣)\max(|u_L - u_R|, |v_L - v_R|)。 这等价于：

max⁡(max⁡i,j∣uLi−uRj∣,max⁡i,j∣vLi−vRj∣)\max \left( \max_{i,j} |u_{L_i} - u_{R_j}|, \quad \max_{i,j} |v_{L_i} - v_{R_j}| \right)

其中 uLi,vLiu_{L_i}, v_{L_i} 是小 L 的第 ii 个选择变换后的坐标， uRj,vRju_{R_j}, v_{R_j} 是小 R 的第 jj 个选择变换后的坐标。

问题被分解成了两个独立的部分，喵~

  1. 找到最大的 ∣uL−uR∣|u_L - u_R|。
  2. 找到最大的 ∣vL−vR∣|v_L - v_R|。

最后取这两者的最大值就是答案！

我们先来看第一个子问题：如何最大化 ∣uL−uR∣|u_L - u_R|？ 我们有一堆小 L 的 uu 坐标值，记作集合 ULU_L。还有一堆小 R 的 uu 坐标值，记作集合 URU_R。要想让它们之间的差的绝对值最大，我们应该从一个集合里选出最大值，从另一个集合里选出最小值，对吧？ 所以，

max⁡∣uL−uR∣=max⁡(max⁡(UL)−min⁡(UR),max⁡(UR)−min⁡(UL))\max |u_L - u_R| = \max(\max(U_L) - \min(U_R), \quad \max(U_R) - \min(U_L))

同理，对于 vv 坐标也是一样的：

max⁡∣vL−vR∣=max⁡(max⁡(VL)−min⁡(VR),max⁡(VR)−min⁡(VL))\max |v_L - v_R| = \max(\max(V_L) - \min(V_R), \quad \max(V_R) - \min(V_L))

好耶！思路清晰了！我们的算法步骤就是：

  1. 初始化四个变量来记录小 L 的 u,vu, v 坐标的最大值和最小值：max_u_L, min_u_L, max_v_L, min_v_L。
  2. 遍历小 L 的所有 nn 个速度向量 (x,y)(x, y)，计算出对应的 u=x+yu=x+y 和 v=x−yv=x-y，并用它们来更新这四个最值。
  3. 对小 R 也做同样的事情，得到 max_u_R, min_u_R, max_v_R, min_v_R。
  4. 计算 uu 坐标的最大可能差值：dist_u = max(max_u_L - min_u_R, max_u_R - min_u_L)。
  5. 计算 vv 坐标的最大可能差值：dist_v = max(max_v_L - min_v_R, max_v_R - min_v_L)。
  6. 最终的答案就是 max(dist_u, dist_v)！

这个算法只需要分别遍历一次小 L 和小 R 的所有选择，非常高效，喵~

代码实现 ​

下面就是本喵根据上面的思路，精心准备的C++代码啦！注释写得很详细，希望能帮助你理解哦~

cpp
#include <iostream>
#include <algorithm>
#include <vector>

// 使用 long long 防止坐标和或差溢出
using ll = long long;

// 定义一个很大的数作为初始的最小值
const ll INF = 4e9 + 7; // 坐标最大10^9, 和/差最大2*10^9, 用一个更大的数

int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    // 初始化小 L 的 u, v 坐标范围
    // u = x + y, v = x - y
    ll max_u_L = -INF, min_u_L = INF;
    ll max_v_L = -INF, min_v_L = INF;

    // 遍历小 L 的所有可选向量
    for (int i = 0; i < n; ++i) {
        ll x, y;
        std::cin >> x >> y;
        ll u = x + y;
        ll v = x - y;
        
        // 更新 u 和 v 的最值
        max_u_L = std::max(max_u_L, u);
        min_u_L = std::min(min_u_L, u);
        max_v_L = std::max(max_v_L, v);
        min_v_L = std::min(min_v_L, v);
    }

    // 初始化小 R 的 u, v 坐标范围
    ll max_u_R = -INF, min_u_R = INF;
    ll max_v_R = -INF, min_v_R = INF;

    // 遍历小 R 的所有可选向量
    for (int i = 0; i < m; ++i) {
        ll x, y;
        std::cin >> x >> y;
        ll u = x + y;
        ll v = x - y;

        // 更新 u 和 v 的最值
        max_u_R = std::max(max_u_R, u);
        min_u_R = std::min(min_u_R, u);
        max_v_R = std::max(max_v_R, v);
        min_v_R = std::min(min_v_R, v);
    }

    // 计算 u 坐标系下的最大距离
    // 可能是 L 的最大值减 R 的最小值，也可能是 R 的最大值减 L 的最小值
    ll max_dist_u = std::max(max_u_L - min_u_R, max_u_R - min_u_L);

    // 计算 v 坐标系下的最大距离
    ll max_dist_v = std::max(max_v_L - min_v_R, max_v_R - min_v_L);

    // 最终答案是两种坐标系下最大距离的较大者
    std::cout << std::max(max_dist_u, max_dist_v) << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N+M)O(N + M) 我们只需要遍历一次小 L 的 NN 个向量和一次小 R 的 MM 个向量来找出 u,vu, v 坐标的极值。之后是常数时间的计算。所以总的时间复杂度是线性的，非常快哦！

  • 空间复杂度: O(1)O(1) 我们只用了几个变量来存储最大值和最小值，没有使用随输入规模增大的额外存储空间。所以空间复杂度是常数级别的，超级节省内存的说！

知识点总结 ​

这道题的核心是一个非常漂亮的小技巧，值得我们记在小本本上，喵~

  1. 曼哈顿距离与切比雪夫距离的转换: 这是解决网格图中曼哈顿距离相关问题的利器！

    • 曼哈顿距离: ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|
    • 切比雪夫距离: max⁡(∣x1−x2∣,∣y1−y2∣)\max(|x_1 - x_2|, |y_1 - y_2|)
    • 转换公式: 通过坐标变换 u=x+y,v=x−yu=x+y, v=x-y，可以将原坐标系下的曼哈顿距离问题，转化为新坐标系下的切比雪夫距离问题。

      ∣x1−x2∣+∣y1−y2∣=max⁡(∣u1−u2∣,∣v1−v2∣)|x_1 - x_2| + |y_1 - y_2| = \max(|u_1 - u_2|, |v_1 - v_2|)

  2. 最值问题分解: 通过坐标转换，我们将一个耦合的二维最值问题 max⁡(∣xL−xR∣+∣yL−yR∣)\max(|x_L - x_R| + |y_L - y_R|)，分解成了两个独立的一维最值问题 max⁡(∣uL−uR∣)\max(|u_L - u_R|) 和 max⁡(∣vL−vR∣)\max(|v_L - v_R|)，大大简化了求解过程。

  3. 一维最值差: 要最大化两个集合中元素之差的绝对值，即 max⁡∣a−b∣\max|a-b| 其中 a∈A,b∈Ba \in A, b \in B，只需要计算 max⁡(max⁡(A)−min⁡(B),max⁡(B)−min⁡(A))\max(\max(A) - \min(B), \max(B) - \min(A)) 即可。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问本喵哦！一起加油，成为更厉害的算法大师吧，喵~！