torus711 のアレ

主に競技プログラミングの問題について書きます

AtCoder Beginner Contest 168, C : : (Colon)

問題概要

 長針の長さが $A$ ,短針の長さが $B$ で,$H$ 時 $M $ 分を指しているアナログ時計を考える(針は等角加速度で運動する).
 2 つの針の先端同士の距離を求めよ.

制約

  • $1 \leq A, B \leq 1{,}000$
  • $0 \leq H \leq 11$
  • $0 \leq M \leq 59$

準備

 まずは針の角度が分からないと何も分からんって感じなので,針の角度から求めていきます.ちなみに,角度としては弧度法で統一します.短針については,時間の経過による分と分の経過による分を足さなければならないので,$\theta_a = 2 \pi \left( \frac H { 12 } + \frac { \frac M { 60 } } { 12 } \right)$ で,短針については分の経過だけを考えればよいので $\theta_b = 2 \pi \left( \frac M { 60 } \right)$ です.
 円運動に関する問題なので,円運動と相性のよい三角関数を用いて解を求めていきますが,ここでは 2 通りの解法を紹介します.

解法 1 : 角度から座標を求めて距離を計算する

 線分の長さと角度が分かっているとき,三角関数 $\sin, \cos$ を使うとそれぞれ $Y$ 軸成分・$X$ 軸成分を取り出すことができます*1.これを用いると,
\begin{align*}
y_a &= a \sin \theta_a \\
x_a &= a \cos \theta_a \\
y_b &= b \sin \theta_b \\
x_b &= b \cos \theta_b \\
d &= \sqrt{ ( y_a - y_b ) ^ 2 + ( x_a - x_b ) ^2 }
\end{align*}
という風にして針先の座標を求め,Pythagoras の定理から距離 $d$ を求められます.

解法 2 : 余弦定理

 余弦定理というものがあり,これを使うと,三角形の内,2 辺の長さとそれらが挟む角の角度から,残りの辺の長さを求められます.これを用いる場合,
$$
d = \sqrt{ a ^ 2 + b ^ 2 - 2 a b \cos ( \theta_a - \theta_b ) }
$$
として一発で求まります.

コード 1 (Haskell)

main = do
	[ a, b, h, m ] :: [Double] <- map fromIntegral <$> readInts
	let
		theta1 = ( h / 12 + m / 60 / 12 ) * pi * 2
		theta2 = m / 60 * pi * 2
		y1 = a * sin theta1
		x1 = a * cos theta1
		y2 = b * sin theta2
		x2 = b * cos theta2
		d = sqrt $ ( y1 - y2 ) ^ 2 + ( x1 - x2 ) ^ 2
	printf "%.12f\n" d

コード 2 (Haskell)

main = do
	[ a, b, h, m ] :: [Double] <- map fromIntegral <$> readInts
	let
		theta1 = ( h / 12 + m / 60 / 12 ) * 2 * pi
		theta2 =  m / 60 * 2 * pi
		theta = theta1 - theta2
	printf "%.12f\n" $ sqrt ( a ^ 2 + b ^ 2 - 2 * a * b * cos theta )

*1:一応,ぐぐりキーワードとしては「単位円」などで調べるとよいと思います