問題

https://beta.atcoder.jp/contests/arc047/tasks/arc047_b

座標平面上に $N$ つの格子点がある。これらの点はある点 $P$ とマンハッタン距離が同じである。 $P$ としてありうる点を求めよ。

考え方

$x-y$ 座標平面上のある点からのマンハッタン距離が同じ点の軌跡は、座標平面を $45$ 度回転するとある点から正方形を描いた点の軌跡と同じである。

$45$ 度回転後の $u-v$ 座標上で考える $(u : v = x - y = 0, v : u = x + y = 0)$ 。

$u_i = x_i + y_i$
$v_i = x_i - y_i$

正方形の軌跡を描くとき、正方形の辺の長さ $d$ は $d = max(max(u_i)-min(u_i), max(v_i)-min(v_i))$ である。よって正方形の中心となりうる点は、 $u$ 座標は $min(u_i) + d/2, max(u_i) - d/2$ で $v$ 座標は $min(v_i) + d/2, max(v_i) - d/2$ である。高々 $4$ 通りに絞り込むことができたので、あとはそれぞれの点についてシミュレーションして、マンハッタン距離が同じになるか確認すればよい。