2、3回解いているが、なかなか覚えられないのでメモ。 マンハッタン距離が出たら、ひとまず45度回転を考えるのは覚えていた。
45度回転の方法は (X, Y) = (x-y, x+y) を計算すること。 45度回転すると、距離の領域が正方形になり、処理がしやすくなる。
45度回転後のマンハッタン距離は max(|x1 - x2|, |y1 - y2|) になる。
なぜか？
これは チェビシェフ距離 と言うらしい。
下記の記事で紹介されている式変形を眺めると、そうなることが分かってくる。
回転後の解法としては、
一番外側にある点の座標を利用する。 上下左右の一番外側なので(xmin, xmax, ymin, ymax)を求める。 クエリで指定される点と一番外側にある点が最大の距離となる。 そのため、答えは max(|x-xmin|, |x-xmax|, |y-ymin|, |y-ymax|) の値となる。
