アルゴリズム45度回転45 度回転 キーワード 45度回転 マンハッタン距離 概要 (x,y)(x, y)(x,y) 座標を (X,Y)=(x−y,x+y)(X, Y) = (x - y, x + y)(X,Y)=(x−y,x+y) に座標変換する操作。 (x,y)(x, y)(x,y) に π4\frac{\pi}{4}4π の回転行列をかけると、 (12−121212)(xy)=12(x−yx+y)\begin{pmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{pmatrix} \begin{pmatrix} x \\ y \\ \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} x - y\\ x + y \\ \end{pmatrix}(2121−2121)(xy)=21(x−yx+y) が得られる。 (x,y)(x, y)(x,y) 座標上の 2 点 (x1,y1),(x2,y2)(x_1, y_1), (x_2, y_2)(x1,y1),(x2,y2) のマンハッタン距離は、 d=∣x1−x2∣−∣y1−y2∣=max((x1−x2)+(y1−y2),(x1−x2)+(y2−y1),(x2−x1)+(y1−y2),(x2−x1)+(y2−y1))=max((x1+y1)−(x2+y2),(x1−y1)−(x2−y2),−(x1−y1)+(x2−y2),−(x1+y1)+(x2+y2))=max(X1−X2,Y1−Y2,Y2−Y1,X2−X1)=max(∣X1−X2∣,∣Y1−Y2∣)\begin{equation*} \begin{split} d &= |x_1 - x_2| - |y_1 - y_2| \\ &= \max((x_1 - x_2) + (y_1 - y_2), (x_1 - x_2) + (y_2 - y_1), (x_2 - x_1) + (y_1 - y_2), (x_2 - x_1) + (y_2 - y_1)) \\ &= \max((x_1 + y_1) - (x_2 + y_2), (x_1 - y_1) - (x_2 - y_2), -(x_1 - y_1) + (x_2 - y_2), -(x_1 + y_1) + (x_2 + y_2)) \\ &= \max(X_1 - X_2, Y_1 - Y_2, Y_2 - Y_1, X_2 - X_1) \\ &= \max(|X_1 - X_2|, |Y_1 - Y_2|) \end{split} \end{equation*}d=∣x1−x2∣−∣y1−y2∣=max((x1−x2)+(y1−y2),(x1−x2)+(y2−y1),(x2−x1)+(y1−y2),(x2−x1)+(y2−y1))=max((x1+y1)−(x2+y2),(x1−y1)−(x2−y2),−(x1−y1)+(x2−y2),−(x1+y1)+(x2+y2))=max(X1−X2,Y1−Y2,Y2−Y1,X2−X1)=max(∣X1−X2∣,∣Y1−Y2∣) が成り立つ。 上の等式からわかるように、 (X1,Y1)(X_1, Y_1)(X1,Y1) から等距離の点は、 (X1,Y1)(X_1, Y_1)(X1,Y1) を中心(対角線の交点)とする正方形上に存在する。 計算量 変形自体は O(1)\mathrm{O}(1)O(1) 応用例 最大距離の点の取得 等距離の点の取得 例題 典型 90 | 036 - Max Manhattan Distance(★5) (opens in a new tab) 引用 https://scrapbox.io/magurofly/%E3%83%9E%E3%83%B3%E3%83%8F%E3%83%83%E3%82%BF%E3%83%B3%E8%B7%9D%E9%9B%A2%E3%81%A845%E5%BA%A6%E5%9B%9E%E8%BB%A2 (opens in a new tab) UnionFindBFS