[mathjax]
最近なにもやる気が起きません。と言いながらwarframeやってるんですけどね。楽しい。
「流石にやってない問題たまりすぎてるなあ」と思って授業中暇だったので、溜まってた問題を解いてました。そしたら、60分かかってしまった問題があったので、備忘録として残しておきます。いつか使いそうなので証明も書いときます。
目次
自分が書いたコード
#include <iostream> | |
#include <math.h> | |
using namespace std; | |
int main(int argc, char const *argv[]) { | |
double x1,y1,x2,y2; | |
cin>>x1>>y1>>x2>>y2; | |
double dis,a,x3,y3,x4,y4; | |
dis=sqrt(pow(x1-x2,2)+pow(y1-y2,2)); | |
if(x1!=x2){ | |
a=(y1-y2)/(x1-x2); | |
if(a!=0){ | |
if(y1<=y2){ | |
x4=x1-dis*sqrt(pow(a,2)/(pow(a,2)+1)); | |
y4=(x1-x4)/a+y1; | |
x3=x2+(x4-x1); | |
y3=y2+(y4-y1); | |
}else{ | |
x4=x1+dis*sqrt(pow(a,2)/(pow(a,2)+1)); | |
y4=(x1-x4)/a+y1; | |
x3=x2+(x4-x1); | |
y3=y2+(y4-y1); | |
} | |
}else{ | |
x3=x2; | |
x4=x1; | |
if(x1<x2){ | |
y3=y2+dis; | |
y4=y3; | |
}else{ | |
y3=y2-dis; | |
y4=y3; | |
} | |
} | |
}else{ | |
y3=y2; | |
y4=y1; | |
if(y1<y2){ | |
x3=x2-dis; | |
x4=x1-dis; | |
}else{ | |
x3=x2+dis; | |
x4=x1+dis; | |
} | |
} | |
printf("%.0f %.0f %.0f %.0f\n",x3,y3,x4,y4); | |
return 0; | |
} |
なんともクソみたいなコードですね。しかし、これはもっと短く書けたみたいです。
[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}
\)