ARC047-B:同一円周上

問題

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

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

考え方

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

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

Submission #3501748 - AtCoder Regular Contest 047

ポイント

  • マンハッタン距離は45度回転
  • 無限の候補を有限の候補に絞り込む

類題