# 📚 竞赛算法讲义：从曼哈顿距离到切比雪夫距离

## 一、 距离的定义

在二维平面上，给定两点 $P\_1(x\_1, y\_1)$ 和 $P\_2(x\_2, y\_2)$：

1. **欧几里得距离 (Euclidean Distance)**：直线距离
   $$d\_E = \sqrt{(x\_1 - x\_2)^2 + (y\_1 - y\_2)^2}$$
2. **曼哈顿距离 (Manhattan Distance)**：只能走横竖网格（比如出租车走格子）
   $$d\_M = |x\_1 - x\_2| + |y\_1 - y\_2|$$
3. **切比雪夫距离 (Chebyshev Distance)**：国际象棋中“王”(King)的移动步数（横、竖、斜都能走一步）
   $$d\_C = \max(|x\_1 - x\_2|, |y\_1 - y\_2|)$$

---

## 二、 核心数学桥梁：坐标系旋转 (45° 旋转变换)

在处理复杂的几何极值、矩形覆盖或多点最值问题时，**曼哈顿距离**由于带有绝对值求和，直接用数据结构（如线段树）维护非常困难。

而通过**坐标旋转 45°**，可以将**曼哈顿距离**等价转化为**切比雪夫距离**。

### 1. 曼哈顿 $\to$ 切比雪夫
对于原坐标系下的点 $(x, y)$，我们将其变换为新坐标 $(u, v)$：
$$\begin{cases} u = x + y \\ v = x - y \end{cases}$$
**性质**：原坐标系中任意两点 $(x\_1, y\_1)$ 和 $(x\_2, y\_2)$ 的**曼哈顿距离**，等于它们在新坐标系 $(u, v)$ 下的**切比雪夫距离**：
$$|x\_1 - x\_2| + |y\_1 - y\_2| = \max(|u\_1 - u\_2|, |v\_1 - v\_2|)$$

### 2. 切比雪夫 $\to$ 曼哈顿
反过来，若原坐标系下考虑切比雪夫距离 $\max(|x\_1 - x\_2|, |y\_1 - y\_2|)$，令：
$$\begin{cases} u = x + y \\ v = x - y \end{cases}$$
则它对应原坐标系（旋转后）下的**曼哈顿距离的一半**：
$$\max(|x\_1 - x\_2|, |y\_1 - y\_2|) = \frac{1}{2} (|u\_1 - u\_2| + |v\_1 - v\_2|)$$

---

## 三、 为什么切比雪夫距离好用？

切比雪夫距离的核心优势在于 $\max$ 算子：
$$\max(|x\_1 - x\_2|, |y\_1 - y\_2|) = \max(\max(x\_1, x\_2) - \min(x\_1, x\_2), \max(y\_1, y\_2) - \min(y\_1, y\_2))$$
这意味着：**它把原本横纵坐标耦合在一起的绝对值，拆成了独立的 $X$ 坐标极值和 $Y$ 坐标极值！** 
在处理“求某一个点到所有点的最大距离”时，我们只需要维护所有点的 $x\_{\max}, x\_{\min}, y\_{\max}, y\_{\min}$ 即可，复杂度直接降为 $O(1)$ 或配合线段树 $O(\log n)$。

---

## 四、 Codeforces 经典例题推荐

### 1. CF1093G - Multidimensional Queries (进阶：高维曼哈顿距离)
* **题目大意**：给定 $n$ 个 $k$ 维空间的点，支持单点修改。每次查询某个区间内任意两点间的**最大曼哈顿距离**。
* **考点**：曼哈顿距离在高维空间的去绝对值展开（$2^{k-1}$ 种状态），结合线段树维护。虽然是高维，但其本质依然是利用绝对值不等式进行符号化简。

### 2. CF 经典坐标变换题型：寻找“中心点”
* **题目描述简化**：给你平面上 $n$ 个人的坐标，找出一个最优的建筑位置（$x, y$），使得所有人到这个建筑的**曼哈顿距离之最大值最小**。
* **转化思路**：
  1. 求“最大距离最小”，很显然可以二分答案 $R$，或者利用切比雪夫距离的性质。
  2. 如果要求曼哈顿距离的最大值最小，可以通过坐标变换 $(x+y, x-y)$，把问题转到切比雪夫坐标系下，此时限制条件会变成一个正方形区域的交集。

---

## 五、 模板代码演示（以计算多点最大曼哈顿距离为例）

利用上述讲义中的公式，如果我们在 Codeforces 遇到求 $n$ 个点中**任意两点间最大曼哈顿距离**，代码可以写得非常优雅：

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

using namespace std;

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

int n;
    if (!(cin >> n)) return 0;

long long max_u = -4e18, min_u = 4e18;
    long long max_v = -4e18, min_v = 4e18;

for (int i = 0; i < n; ++i) {
        long long x, y;
        cin >> x >> y;

// 核心：曼哈顿转切比雪夫的坐标变换
        long long u = x + y;
        long long v = x - y;

max_u = max(max_u, u);
        min_u = min(min_u, u);
        max_v = max(max_v, v);
        min_v = min(min_v, v);
    }

// 变换后，最大曼哈顿距离 = 最大切比雪夫距离
    // 即 max( u的最大值 - u的最小值, v的最大值 - v的最小值 )
    long long ans = max(max_u - min_u, max_v - min_v);

cout << ans << "\n";

return 0;
}
```

📚 竞赛算法讲义：从曼哈顿距离到切比雪夫距离

一、距离的定义

在二维平面上，给定两点 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$：

欧几里得距离 (Euclidean Distance)：直线距离 $$d_E = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
曼哈顿距离 (Manhattan Distance)：只能走横竖网格（比如出租车走格子） $$d_M = |x_1 - x_2| + |y_1 - y_2|$$
切比雪夫距离 (Chebyshev Distance)：国际象棋中“王”(King)的移动步数（横、竖、斜都能走一步） $$d_C = \max(|x_1 - x_2|, |y_1 - y_2|)$$

二、核心数学桥梁：坐标系旋转 (45° 旋转变换)

在处理复杂的几何极值、矩形覆盖或多点最值问题时，曼哈顿距离由于带有绝对值求和，直接用数据结构（如线段树）维护非常困难。

而通过坐标旋转 45°，可以将曼哈顿距离等价转化为切比雪夫距离。

1. 曼哈顿 $\to$ 切比雪夫

对于原坐标系下的点 $(x, y)$，我们将其变换为新坐标 $(u, v)$： $$\begin{cases} u = x + y \ v = x - y \end{cases}$$ 性质：原坐标系中任意两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的曼哈顿距离，等于它们在新坐标系 $(u, v)$ 下的切比雪夫距离： $$|x_1 - x_2| + |y_1 - y_2| = \max(|u_1 - u_2|, |v_1 - v_2|)$$

2. 切比雪夫 $\to$ 曼哈顿

反过来，若原坐标系下考虑切比雪夫距离 $\max(|x_1 - x_2|, |y_1 - y_2|)$，令： $$\begin{cases} u = x + y \ v = x - y \end{cases}$$ 则它对应原坐标系（旋转后）下的曼哈顿距离的一半： $$\max(|x_1 - x_2|, |y_1 - y_2|) = \frac{1}{2} (|u_1 - u_2| + |v_1 - v_2|)$$

三、为什么切比雪夫距离好用？

切比雪夫距离的核心优势在于 $\max$ 算子： $$\max(|x_1 - x_2|, |y_1 - y_2|) = \max(\max(x_1, x_2) - \min(x_1, x_2), \max(y_1, y_2) - \min(y_1, y_2))$$ 这意味着：它把原本横纵坐标耦合在一起的绝对值，拆成了独立的 $X$ 坐标极值和 $Y$ 坐标极值！ 在处理“求某一个点到所有点的最大距离”时，我们只需要维护所有点的 $x_{\max}, x_{\min}, y_{\max}, y_{\min}$ 即可，复杂度直接降为 $O(1)$ 或配合线段树 $O(\log n)$。

四、 Codeforces 经典例题推荐

1. CF1093G - Multidimensional Queries (进阶：高维曼哈顿距离)

题目大意：给定 $n$ 个 $k$ 维空间的点，支持单点修改。每次查询某个区间内任意两点间的最大曼哈顿距离。
考点：曼哈顿距离在高维空间的去绝对值展开（$2^{k-1}$ 种状态），结合线段树维护。虽然是高维，但其本质依然是利用绝对值不等式进行符号化简。

2. CF 经典坐标变换题型：寻找“中心点”

题目描述简化：给你平面上 $n$ 个人的坐标，找出一个最优的建筑位置（$x, y$），使得所有人到这个建筑的曼哈顿距离之最大值最小。
转化思路：
求“最大距离最小”，很显然可以二分答案 $R$，或者利用切比雪夫距离的性质。
如果要求曼哈顿距离的最大值最小，可以通过坐标变换 $(x+y, x-y)$，把问题转到切比雪夫坐标系下，此时限制条件会变成一个正方形区域的交集。

五、模板代码演示（以计算多点最大曼哈顿距离为例）

利用上述讲义中的公式，如果我们在 Codeforces 遇到求 $n$ 个点中任意两点间最大曼哈顿距离，代码可以写得非常优雅：

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

using namespace std;

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    long long max_u = -4e18, min_u = 4e18;
    long long max_v = -4e18, min_v = 4e18;

    for (int i = 0; i < n; ++i) {
        long long x, y;
        cin >> x >> y;

        // 核心：曼哈顿转切比雪夫的坐标变换
        long long u = x + y;
        long long v = x - y;

        max_u = max(max_u, u);
        min_u = min(min_u, u);
        max_v = max(max_v, v);
        min_v = min(min_v, v);
    }

    // 变换后，最大曼哈顿距离 = 最大切比雪夫距离
    // 即 max( u的最大值 - u的最小值, v的最大值 - v的最小值 )
    long long ans = max(max_u - min_u, max_v - min_v);

    cout << ans << "\n";

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

切比雪夫距离（Chebyshev Distance） 分享

📚 竞赛算法讲义：从曼哈顿距离到切比雪夫距离

一、 距离的定义

二、 核心数学桥梁：坐标系旋转 (45° 旋转变换)