yukicoder No.105 arcの六角ボルト:解法および解答例
このところ、私はAtCoderで開催されたコンテストの過去問を解き進めるとともに、yukicoderの★★~★★★レベルの問題に取り組み、競技プログラミングの練習をしています。この記事では、昨日解いたNo.105 arcの六角ボルト - yukicoderという問題について、学習の記録を兼ねて、その解き方をまとめ、解答例を示します。
問題の趣旨
xy-平面上にある6点, , , , , を頂点とする正六角形Hがある。原点を中心にHを角度d だけ反時計回りに回転させて、正六角形H'を得た。このときに頂点はそれぞれ点に移った。列を並べ替えたの各項の座標が与えられるので、dを求めよ。
解法
ヒントとして、逆三角関数を使用すると書かれていますが、以下のように複素数を用いて解くこともできます。なお、点に対応する複素数を小文字でと書くことにします。また、複素数zの偏角をarg z(ただし-180°より大きく180°以下であるとする*1)で表します。
場合1:答えが0よりも大きい場合
正六角形の中心と回転の中心がいずれも原点であることに注意すると、各頂点に対応する複素数の偏角の変化がdに等しくなることがわかります。いまは0°, 60°, 120°, 180°, -60°, -120°であるため、あるいはのうちで最小のものをmとすると、m = -180°+ dとなります。よって、dはこれに180°を加えた値に等しくなります。
場合2:答えが0にほぼ等しく、誤差の影響が大きい場合
基本的には上の考え方でよいのですが、入力値および浮動小数点数の誤差により、dがほとんど0に等しいときには不都合が生じることがあります。数εを0にほぼ等しい正の数とすれば、この場合にはのうちで最小のものがm = -120° - εとなることがあります*2。ここで場合1と同様に180°を加えると、m + 180° = 60° - εとなり、これは[0°, 50°)に収まりません。これを利用して場合2を場合1と区別することができます。
まとめ
結局、この問題は以下の方法で解けます。まずは、場合1について述べた方法に従い、m + 180°を求めます。それが[0°, 50°)に収まれば、そのまま答えdとなります。さもなければ、答えは0°となります。
解答例
HaskellおよびC++11で書いたものを以下に示します。上記で定めた偏角の範囲「-180°より大きく180°以下である」は、Haskellのphase関数(モジュールData.Complexで定義されている)およびC++のstd::arg関数(ヘッダcomplexが必要となる)の返り値の範囲と一致させています。ただし返り値は弧度法(ラジアン)で与えられるため、変換が必要となります。場合1と場合2を判別するために、計算値を55°と比較しています。この55°という値にはさほど深い意味はありません。(50°, 60°)から適当に選べば十分です。
Haskellによる解答例
C++11による解答例
感想
複素数をつかって三角形の外心を求める - ゆらのふなびとという記事のおかげで、図形にまつわる競技プログラミングの問題は複素数を用いて容易に解けることがあると知りました。これを踏まえ、図形の問題を目にした際には複素数の使用も考慮するようになりました。この問題を通じて、複素数の有用性を改めて感じました。
実のところ、この問題には数ヶ月前にも挑戦したのですが、そのときにはっきりとした方針が立ちませんでした。ただ、大して試行錯誤したわけでもないのに諦めて後回しにしてしまったようです。ときどきそのような過ちを犯すことがあるので、気をつけたいものです。