読者です 読者をやめる 読者になる 読者になる

はむ吉(のんびり)の練習ノート

主にプログラミングについて、思いついたことや、試してみたこと、学んだことを、覚え書きを兼ねてまとめます。

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

yukicoder 幾何

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

問題の趣旨

xy-平面上の3つの格子点*1\mathrm{P}_k(X_k, Y_k)\:(k=1,2,3)が与えられる。ある格子点\mathrm{P}_4(X_4, Y_4)が存在し、4点\mathrm{P}_1, \mathrm{P}_2, \mathrm{P}_3, \mathrm{P}_4が正方形をなすときに、\mathrm{P}_4(X_4, Y_4)を求めよ。

方針

f:id:hamukichi_nbr:20160811202819p:plain

正方形をつくれる場合を考えましょう。このときに、\mathrm{P}_1, \mathrm{P}_2, \mathrm{P}_3, \mathrm{P}_4を適当に並べ替えて\mathrm{Q}_1, \mathrm{Q}_2, \mathrm{Q}_3, \mathrm{Q}_4 = \mathrm{P}_4とすれば、上図のようにこれらが並ぶはずです。このときに、点\mathrm{Q}_2のまわりに点\mathrm{Q}_3を反時計回りに\pi / 2 rad(すなわち90°)だけ回転させると、点\mathrm{Q}_1に一致します。また、点\mathrm{Q}_1のまわりに点\mathrm{Q}_2を反時計回りに\pi / 2 radだけ回転させると、点\mathrm{Q}_4に移ります。

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

したがって、与えられた3点\mathrm{P}_k(X_k, Y_k)\:(k=1,2,3)の並べ替えを最大3!通り試し、上の方法で点\mathrm{P}_4(X_4, Y_4)が見つかればそれを出力すればよいということになります。

実装

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


感想

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

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

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