曼哈顿距离
$$ d = |x_1 - x_2| + |y_1 - y_2| $$
切比雪夫距离
$$ d = \max(|x_1 - x_2|, |y_1 - y_2|) $$
曼哈顿距离转切比雪夫距离
$$ \begin{aligned} d &= |x_1 - x_2| + |y_1 - y_2| \\ &= \max\{x_1 - x_2 + y_1 - y_2, \space x_2 - x_1 + y_2 - y_1, \space x_1 - x_2 + y_2 - y_1, \space x_2 - x_1 + y_1 - y_2,\} \\ &= \max\{|(x_1 + y_1) - (x_2 + y_2)|, \space |(x_1 - y_1) - (x_2 - y_2)|\} \end{aligned} $$
这其实就是 $(x_1 + y_1, x_1 - y_1), (x_2 + y_2, x_2 - y_2)$ 两点的切比雪夫距离。
所以 $(x, y) \to (x + y, x - y)$，新坐标系下的切比雪夫距离 = 原坐标系下的曼哈顿距离
切比雪夫距离转曼哈顿距离
$$ \begin{aligned} d &= \max(|x_1 - x_2|, |y_1 - y_2|) \\ &= \max\{x_1 - x_2, \space x_2 - x_1, \space y_1 - y_2, \space y_2 - y_1\} \\ &=\max \begin{cases} \frac{x_1 + y_1}{2} + \frac{x_1 - y_1}{2} - \frac{x_2 + y_2}{2} - \frac{x_2 - y_2}{2} \\ \frac{x_2 + y_2}{2} + \frac{x_2 - y_2}{2} - \frac{x_1 + y_1}{2} - \frac{x_1 - y_1}{2} \\ \frac{x_1 + y_1}{2} + \frac{y_1 - x_1}{2} - \frac{x_2 + y_2}{2} - \frac{y_2 - x_2}{2} \\ \frac{x_2 + y_2}{2} + \frac{y_2 - x_2}{2} - \frac{x_1 + y_1}{2} - \frac{y_1 - x_1}{2} \end{cases} \\ &= |\frac{x_1 + y_1}{2} - \frac{x_2 + y_2}{2}| + |\frac{x_1 - y_1}{2} - \frac{x_2 - y_2}{2}| \end{aligned} $$
这其实就是 $(\frac{x_1 + y_1}{2}, \frac{x_1 - y_1}{2}), (\frac{x_2 + y_2}{2}, \frac{x_2 - y_2}{2})$ 两点的曼哈顿距离。
所以 $(x, y) \to (\frac{x + y}{2}, \frac{x - y}{2})$，新坐标系下的曼哈顿距离 = 原坐标系下的切比雪夫距离
P3964
题意：给定一些点，选其中一个点使其他点到这个点的切比雪夫距离之和最小，求出最小距离。
切比雪夫距离带个 max 不太好做，考虑转成曼哈顿距离。令点所有点 $(x, y) \to (\frac{x + y}{2}, \frac{x - y}{2})$。
考虑算贡献，假设选了点 $(x_i, y_i)$。先考虑横坐标，设前 $k$ 个点的横坐标都 $< x_i$，那么所有点横坐标的贡献和是
$$ \sum_{j = 1}^{k} (x_i - x_j) + \sum_{j = k + 1} ^ {n} (x_j - x_i) \\ = kx_i - \sum_{j = 1}^k x_j + \sum_{j = k + 1}^n x_j - (n - k)x_i $$
纵坐标计算方法同上。
排个序，$k$ 可以直接二分求出来，贡献可以通过前缀和算出来。