AtCoder ABC218
ABC218参加しました。
簡単な問題は省略します。今回はCだけ。
C - Shapes
解説 - AtCoder Beginner Contest 218
提出 #25798573 - AtCoder Beginner Contest 218
ちょっと実装量が多いです。
問題はD - Congruence Pointsが近いと思います。
自分のコードは公式解説版(Solve2())と重心を移動させる版(SolveMain())があります。
公式解答の方針は最初に思い立ったのですが、なぜかうまくいかなかったので、重心移動版を考えました。
重心移動版は、まずS,Tの重心を求めて、それを原点(0,0)に平行移動させます。
回転はS,Tの重心を中心に行えば、後は完全一致するかどうかを見ればいい、という方針に立っています。
この方針だと、重心がどうしても浮動小数点になってしまうため、後の演算を全てを浮動小数点で考えないといけなくなる点がネックです。回転後でS,Tが一致するかを見るとき(CheckSamePoints())に、(浮動小数点演算の誤差をごまかすために)ちょっと無理やりなことをしています。ただ、これをしないと、ソートができず、その場合はO(N4) になるので、如何ともし難いです。
また、この回答だと、入力の「マス目」(＝全て整数点入力)という制約をうまくいかせませんね... ABC207Dを参考に実装したので、そうなっちゃいますが...
制約にある「90度回転のみ」だと、全て整数演算で補えるため、浮動小数点演算に悩まされることはないのが、公式解答のいいところだと思います。
あと、大切なのが、S,Tの中の#の数が一致するかどうかの判定。#がある部分しか考えてないコードなので、これを忘れると、REやWAが出てしまいます。こういう「答えが明らか」なケース(今回は一致しない場合は明らかに Noが答え)は、コードに入れてあげると安心です。また、こういうケースは経験上、アルゴリズムのエッジケースになることが多い気がします。
感想
浮動小数点演算をしなくていいように、整数入力で、しかもグラフではなくマス目入力になっているところにちゃんと気がつく必要がありました。あとは、幾何ライブラリについては整数版があるといいかもしれない。
