ARC047-B:同一円周上

問題

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

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

Submission #3767743 - AtCoder Regular Contest 047

ポイント

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

類題