チェビシェフ距離への置き換えを利用して（k次元）マンハッタン距離の最大値を求める方法 - naoya_t@hatenablog

LeetCode Weekly Contest 146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ...概要を表示 LeetCode Weekly Contest 146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。 内容的には マンハッタン距離が最大である2点を選ぶ問題 - ICPC突破専用ザク を理解する過程で噛み砕いたものなので、上記記事を既読の方は本稿を読むには及ばない。 MathJaxの不具合なのか、の下にが書けなかったのでで代用。 2次元の場合 例題 N個の点の二次元座標が与えられ、2点間のマンハッタン距離 を考えた時、マンハッタン距離の最大値を求めよ。 愚直にやると全てのペア（組ある）について距離を算出することになって計算量は（kは次元数=2）になり、のような制約だと時間内に解くことができない。 という写像を考える。 $$ \begin{align} &ManhattanDistance( (x_i,y_i), (x_j,y_j) ) \\ &= |x_i-x