yukicoder No.55 正方形を描くだけの簡単なお仕事です。：解き方とRubyによる実装

少しずつ、yukicoderにある★★～★★★レベルの問題を解き進めています。この記事では、先ほど解いたNo.55 正方形を描くだけの簡単なお仕事です。 - yukicoderという問題について、解き方とRubyによるコードを示します。最近ブログに「解説」をあまり書いていなかったので、そのリハビリ(?)も兼ねています。

問題の趣旨

xy-平面上の3つの格子点*1が与えられる。ある格子点が存在し、4点が正方形をなすときに、を求めよ。

方針

正方形をつくれる場合を考えましょう。このときに、を適当に並べ替えてとすれば、上図のようにこれらが並ぶはずです。このときに、点のまわりに点を反時計回りに rad（すなわち90°）だけ回転させると、点に一致します。また、点のまわりに点を反時計回りに radだけ回転させると、点に移ります。

ここで頻出している「点○○のまわりに点××を角度△△だけ回転させる」という操作、すなわち、与えられた点を、位置ベクトルがである点Cを中心として、反時計回りにθ [rad]だけ回転させるという操作を考えましょう。これは、与えられた点をだけ平行移動し、原点を中心として反時計回りにθ [rad]だけ回転し、だけ平行移動することと同じです。平行移動は単純に座標の足し引きで表せ、回転移動はwikipedia:回転行列を使って表現できます*2。

したがって、与えられた3点の並べ替えを最大3!通り試し、上の方法で点が見つかればそれを出力すればよいということになります。

実装

今回はRubyで解きました。配列の順列をつくるメソッドや行列・ベクトルが標準ライブラリに含まれていることが主な理由でした。

感想

Rubyの標準ライブラリの有用性を感じました。ただ、時間制限の厳しい問題ではこれに頼っているとTLEしかねません。そのため、そろそろ行列・ベクトルにまつわるC++用ライブラリを自分で整備する必要がありそうです。

*1:この記事では、x, y両座標が整数である点を格子点と呼ぶことにします。

*2:参考： 変換の行列表現