AtCoder Beginner Contest 207 [ D - Congruence Points ] をPythonで解く。やたら高難易度で参加者をザワつかせたD問題(400点、🟨黄色diff）
ABCのD問題に高難易度問題が突如あらわれ、コンテスト参加者をザワつかせたこの問題。
多分にもれず、ワタクシも解けてませんが勉強として、解説みてやってみました。
解法
色々な解法が紹介されてますが、一番シンプルと思われる公式解説で説明されている方法を実装してみます。
- 点集合S, Tの重心を計算する
- S, Tの座標を重心からの相対座標に変換
- Sの重心と一致しない点とTiの点の相対的な角度をatan2で計算。Siを回転させてみる。SiがTのどこかの点と一致するか判定
- 回転させた結果、SとTの点がすべて一致することがわかったらYes。それ以外はNo
- N==1の時、一致するのは自明なのでYes
実装
公式解説のC++の実装を参考にしてますが、一部違う点もあります。
公式のC++コードでは、重心座標をNで割らずに座標をN倍して、数字が小さくなることによる計算誤差の回避がされています。
ですがPythonで書いてみたところ、この処理にならわなくても普通に動いたので、素直に重心計算しています。
