[mathjax]
最近なにもやる気が起きません。と言いながらwarframeやってるんですけどね。楽しい。
「流石にやってない問題たまりすぎてるなあ」と思って授業中暇だったので、溜まってた問題を解いてました。そしたら、60分かかってしまった問題があったので、備忘録として残しておきます。いつか使いそうなので証明も書いときます。
目次
自分が書いたコード
なんともクソみたいなコードですね。しかし、これはもっと短く書けたみたいです。
[blogcard url=”https://beta.atcoder.jp/contests/abc108/submissions/3331075″]
とてもシンプルです。しかし、ここまでシンプルにできるのか？と思ったので、ちゃんと計算してみました。
式の証明(面倒くさい方法)
計算式
\(A(x_1,y_1),B(x_2,y_2),C(x_3,y_3),D(x_4,y_4)\)とおく。
また、線分ABの距離disと傾きaを求めると、
\(AB=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} \tag{1}\)
\(a=\frac{y_1-y_2}{x_1-x_2} \tag{2}\)
となる。
ただし、\(x_1\neq x_2\)、\(a \neq 0\)である。
また、線分ADは線分ABに垂直なので、
\(\frac{y_1-y_4}{x_1-x_4} \times a =-1 \tag{3}\)
である。(3)式を変形して、
\(y_3=y_2+\frac{1}{a}(x_2-x_3) \tag{4}\)
である。さらに、線分BCの距離は
\(BC =\sqrt{(x_2-x_3)^2+(y_2-y_3)^2} \tag{5}\)
である。ここで、線分ABと線分BCの長さは等しいから
\(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} = \sqrt{(x_2-x_3)^2+(y_2-y_3)^2} \tag{6}\)
(6)式に(4)を代入して変形する。
\( (1 + \frac{1}{a^2})x_3^2 – 2(1 + \frac{1}{a^2})x_2 \cdot x_3 + {(1+ \frac{1}{a^2})x_2^2 – AB^2} = 0 \tag{7} \)
(7)式を\(x_3\)について解いて整理すると、
\(x_3 = x_2 \pm \frac{AB}{\sqrt{1 + \frac{1}{a^2}}} \tag{8}\)
となる。ところで、(1)式を(2)式を用いて変化すると、
\(AB=(y_1-y_2) \sqrt{( \frac{x_1-x_2}{y_1-y_2} )^2 + 1} \tag{9}\)
であるので、(9)式を(8)式に代入して
\(x_3=x_2 \pm (y_1-y_2) \tag{10}\)
となる。
問題の条件より各頂点はABCDの順に反時計回りに設定するので、\(x_2\)と\(x_3\)の位置関係より、
\(x_3=x_2+(y_1-y_2) \tag{11} \)
と求められる。(11)式を(4)式に代入して、
\(y_3 = y_2 + (x_2 – x_1) \tag{12} \)
となる。\(x_4とy_4\)を求めるには、頂点Bから頂点Cまでの\(xの増加度とyの増加度\)を求め、それを\(x_1\)の座標に足せば求められる。
うーん・・・めんどくさい！！！とってもめんどくさい！！なにこれ！！！
しかし、ちゃんとシンプルなコードにかかれている式が出てきていますね。ただ、これはめんどくさすぎる。なので、もっと楽に示します。
式の証明(行列を利用)
問題をもっと簡単にすると、どちらかの頂点を中心として、もう一方の頂点を90度回転させればいいので、回転行列を用いれば一発です。
点Bを点A中心に90度回転させると点Cと一致する。
\( \left(
\begin{array}{ccc}
x_3 \\
y_3 \\
\end{array}
\right)
=
\left(
\begin{array}{ccc}
x_2-x_1 \\
y_2-y_1 \\
\end{array}
\right)
\cdot
\left(
\begin{array}{ccc}
\cos 90^\circ & – \sin 90^\circ \\
\sin 90^\circ & \cos 90^\circ \\
\end{array}
\right) \\
\)
これを計算して、\(x方向にx_1、y方向にy_1平行移動\)すると、(11)式、(12)式と同様の結果が得られる。
友人にLINEで「こういう問題あって、こういう示し方したんだけど、いい感じのない？」と聞いたら「回転行列使え」と来て、膝から崩れ落ちました。また人生を無駄にしてしまった。
電気ばっかやってると、複素数とかラプラス変換あたりをよくつかって、行列をあまり使わないので完全に忘れてました。とおもったら、制御で線形代数使ってるわ。ちゃんと勉強してないだけでした。
まとめ
二点が与えられて正方形を作る場合、残りの点の座標は次のようになります。(反時計回りに正方形の頂点を設定しています。)
このとき、残りの2点C,Dの座標は次のように計算できる。
\(点C \begin{cases}
x_3=x_2+(y_1-y_2) \\
y_3=y_2+(x_2-x_1)
\end{cases}
\)
\(点D \begin{cases}
x_4=x_1+(y_1-y_2) \\
y_4=y_1+(x_2-x_1)
\end{cases}
\)