ARC047-B:同一円周上
問題
https://beta.atcoder.jp/contests/arc047/tasks/arc047_b
座標平面上に つの格子点がある。これらの点はある点 とマンハッタン距離が同じである。 としてありうる点を求めよ。
考え方
座標平面上のある点からのマンハッタン距離が同じ点の軌跡は、座標平面を 度回転するとある点から正方形を描いた点の軌跡と同じである。
度回転後の 座標上で考える 。
正方形の軌跡を描くとき、正方形の辺の長さ は である。よって正方形の中心となりうる点は、 座標は で 座標は である。高々 通りに絞り込むことができたので、あとはそれぞれの点についてシミュレーションして、マンハッタン距離が同じになるか確認すればよい。
Submission #3767743 - AtCoder Regular Contest 047
ポイント
- マンハッタン距離は 度回転
- 無限の候補を有限の候補に絞り込む
- 軸と 軸は独立