（この記事は以前はてなブログに投稿していた自分の記事をZennに移植したものです）
この記事は競技プログラミングにおけるマンハッタン距離45度回転を理解しようとするものです。
僕のような数学の素養がない人も理解できるようになっていると思います。
なお、本記事には以下の問題のネタバレが含まれるので注意してください。
・ABC178 E Dist Max
・典型90 036 - Max Manhattan Distance（★5）
また、以下の記事等を参考にしています。
マンハッタン距離45度回転とは何か？
ある任意の2点 (x_i,y_i), (x_j,y_j) のマンハッタン距離 |x_i - x_j| + |y_i - y_j| を考えます。
このとき以下のように式を変形することができます。（よくわからない変形が続くかもしれませんが後で解説します）
\begin{align*}
|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( (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)) \\
&= \max( (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)) \\
&= \max(|(x_i + y_i) - (x_j + y_j)|, \ |(x_i - y_i) - (x_j - y_j)|) \\
\end{align*}
ここで、z_i = x_i + y_i, w_i = x_i − y_i とすると、
|x_i − x_j | + |y_i − y_j | = \max(|z_i − z_j |, \ |w_i − w_j |)
と変形することができます。
これがマンハッタン距離45度回転と呼ばれている計算方法です。
マンハッタン距離45度回転によって、任意の2点間のマンハッタン距離の最大値が高速に求められるなどのメリットがあります。
図で確認するとこのようになります。（(x,y) の回転後の座標を (x',y') = (x-y, x+y) とします）
回転前、点 A と各点のマンハッタン距離はどれも 4 です。
回転すると、点 A とのマンハッタン距離が 4 の点が図のオレンジの正方形上に並びます。
つまり、回転前のマンハッタン距離 = 回転後のチェビシェフ距離（座標の差の最大値） となります。(参考記事3「マンハッタン距離は45度回転させて考える（図示）X=x-y; Y=x+y」より引用)
では、なぜこのような式変形が可能なのか1つずつ見ていきましょう。
式変形
まず前提として |a-b| = \max(a-b, \ b-a) です。
前提の説明
絶対値の定義から確認します。
|x| = \begin{cases}
x &\quad \text{if} \quad x \geq 0 \\
-x &\quad \text{if} \quad x < 0
\end{cases}
ここで x = a -b とすると |a-b| は以下のように考えられます。
|a-b| = \begin{cases}
a-b &\quad \text{if} \quad a-b \geq 0 \\
-(a-b) = b - a &\quad \text{if} \quad a-b < 0
\end{cases}
よって、 |a-b| = \max(a-b, \ b-a) です。
|a-b| = \max(a-b, \ b-a) より、
|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)
と変形できます。
この式をまとめてやると、
\begin{align*}
&\max(x_i - x_j, \ x_j - x_i) + \max(y_i - y_j, \ y_j - y_i) \\
&= \max( (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))
\end{align*}
に変形できます。
これをさらに i, j ごとに並べ替えると、
\begin{align*}
&\max( (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)) \\
&= \max( (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))
\end{align*}
に変形できます。
ここで再び |a-b| = max(a-b, \ b-a) より、
\begin{align*}
&\max( (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)) \\
&= \max(|(x_i + y_i) - (x_j + y_j)|, \ |(x_i - y_i) - (x_j - y_j)|)
\end{align*}
に変形できました。
では実際に問題を解いてみましょう。
ABC178 E Dist Max
問題はこちらです。
https://atcoder.jp/contests/abc178/tasks/abc178_e
任意の2点間のマンハッタン距離の最大値を求める問題です。
愚直にやると O(N^2) かかりそうですが、マンハッタン距離45回転を利用すると高速に解くことができます。
z_i = x_i + y_i, w_i = x_i − y_i とすると、
|x_i − x_j | + |y_i − y_j | = max(|z_i − z_j|, |w_i − w_j |)
となるのでした。
したがって、1\leq i \leq N, 1 \leq j \leq N について \max(\max(|z_i − z_j|, |w_i − w_j |)) が答えとなります。
つまり、任意の2点間のマンハッタン距離の最大値は \max(|z_i − z_j|の最大値, |w_i − w_j |の最大値) です。
ここで、|z_i − z_j| の最大値を考えます。
これは単純に \max(|z_i − z_j|) = (zの最大値) - (zの最小値) です。
z の最大値、最小値は各点の z の値を計算しておくことで O(N) で求められます。
w についても同様に求められるので、O(N) でこの問題を解くことができました。
実装例
典型90 036 - Max Manhattan Distance（★5）
問題はこちらです。
https://atcoder.jp/contests/typical90/tasks/typical90_aj
ある点と N 個の点のマンハッタン距離の最大値を求めるクエリに答える問題です。
この問題も先ほどと同じように考えることができます。
今回の問題では点 P_q のマンハッタン距離の最大値を求める必要があるため、
\max(|z_i − z_q|) = \max( (zの最大値) - z_q, z_q - (zの最小値)) となります。（1 \leq i \leq N）
w についても同様に考えると、
マンハッタン距離の最大値 = max( (zの最大値) - z_q, z_q - (zの最小値), (wの最大値) - w_q, w_q - (wの最小値))
となります。
最大値・最小値をあらかじめ求めておくと O(N+Q) でこの問題を解くことができます。
実装例
Discussion