マンハッタン距離は45°回転
/icons/hr.icon
はじめに
$ (x_i, y_i)と$ (x_j, y_j)のマンハッタン距離は$ |x_i - x_j| + |y_i - y_j|で表されます。
競プロをしていると マンハッタン距離は$ 45^{\circ}回転して考える とよく言われますが、回転させることで何が良いのか考えていきます。
/icons/hr.icon
例題
次の問題を考えます
1054diff
問題概要
二次元ユークリッド平面畳に$ N個の点があります。
$ i \: (1 \leq i \leq N)個目の点の座標は$ (x_i, y_i)です。
異なる$ 2点のマンハッタン距離の最大値を求めよ。
つまり、$ i番目と$ j番目の組み合わせのマンハッタン距離が最も大きい時の$ |x_i - x_j| + |y_i - y_j|を求める問題です。
解説
絶対値が入ったままでは考えにくいのでまずは式変形をしていきます。
$ \begin{aligned} |x_i - x_j| + |y_i - y_j| &= \max(x_i - x_j, x_j - x_i) + \max(y_i - y_j, y_j - y_i) \\ &= \max\left\{ (x_i - x_j) + (y_i - y_j), (x_i - x_j) + (y_j - y_i), (x_j - x_i) + (y_i - y_j), (x_j - x_i) + (y_j - y_i)\right\} \\ &= \max \left\{ (x_i + y_i) - (x_j + y_j), (x_i - y_i) - (x_j - y_j), -(x_i - y_i) + (x_j - y_j), -(x_i + y_i) + (x_j + y_j) \right\} \end{aligned}
だいぶ複雑な式変形になってしまいましたが、ここまで変形すると$ (x_i + y_i)と$ (x_i - y_i)の形のみで表すことができます。
したがって、$ a_i = x_i + y_i, b_i = x_i - y_iとします。
すると、以下のように元の問題文を落とし込むことができます。
$ \begin{aligned} |x_i - x_j| + |y_i - y_j| &= \max \left( a_i - a_j, b_i - b_j, -b_i + b_j, -a_i + a_j \right) \\ &= \max \left( a_i - a_j, -(a_i - a_j), b_i - b_j, -(b_i - b_j) \right) \\ &= \max \left( |a_i - a_j|, |b_i - b_j| \right) \\ &= \max_{1 \leq i \leq N, 1 \leq j \leq N} \left( |a_i - a_j|, |b_i - b_j| \right) \end{aligned}
ここで、$ |a_i - a_j|と$ |b_i - b_j|は互いに独立しているので別々に考えることができます。
したがって、
$ \begin{aligned} \max_{1 \leq i \leq N, 1 \leq j \leq N} |x_i - x_j| + |y_i - y_j| &= \max \left( \max_{1 \leq i \leq N, 1 \leq j \leq N} |a_i - a_j|, \max_{1 \leq i \leq N, 1 \leq j \leq N} |b_i - b_j| \right) \\ &= \max \left( \max_{1 \leq i \leq N} a_i - \min_{1 \leq i \leq N} a_i, \max_{1 \leq i \leq N} b_i - \min_{1 \leq i \leq N} b_i \right) \end{aligned}
となります。
これらの各要素は$ O(N)で求めることができるため、後はやるだけになります。
code:python
N = int(input())
A, B = [], []
for _ in range(N):
a, b = map(int, input().split())
A.append(a + b)
B.append(a - b)
print(max(max(A) - min(A), max(B) - min(B)))
/icons/hr.icon