概要

反射光の計算を頑張るのもよいですが，より簡単に・より高速に 解くことができます．

問題原案：uni_kakurenbo

解説

$2$ 通りの解法を紹介します：

• タンジェントの加法定理を用いて反射の様子を実際にシミュレーションする．(やや重実装)
• 反射光を直線に展開して考える．(一行で書ける)

以下，直線 $Px - Qy = 0$ を 鏡 $\mathrm{S}$，直線 $y = 0$ を 鏡 $\mathrm{T}$ と呼ぶことにします．

実際にシミュレーションをする解法

反射角を考える

$\theta, \alpha, \beta$ をそれぞれ，鏡 $\mathrm{S}$, 入射光, 反射光 の傾きとします．
反射の様子を考えると，これらの間に次のような関係が成り立つことが分かります：

• $\alpha + \beta = 2 \theta$

ここで，$\tan \beta$ を $\tan \theta \; (= \frac{P}{Q})$ および $\tan \alpha$ を用いて表すことを考えます．
$\tan$ の加法定理

• $\displaystyle \tan (\theta_0 \pm \theta_1) = \frac{\tan \theta_0 \pm \tan \theta_1}{1 \mp \tan \theta_0 \tan \theta_1}$ (複号同順)

を用いると，

• $\displaystyle \tan \beta = \tan(2\theta - \alpha) = \frac{\tan \theta (\tan \theta \tan \alpha + 2) - \tan \alpha}{\tan \theta (2 \tan \alpha - \tan \theta) + 1}$

を得ます．

したがって，傾き $k$ の光線が 鏡 $\mathrm{S}$ で反射した後の傾き $k'$ は次のように表されます：

• $\displaystyle k' = \frac{t (t k + 2) - k}{t (2 k - t) + 1 }$
• ただし，$\displaystyle t \coloneqq \frac{P}{Q}$

なお，鏡 $\mathrm{T}$ で反射したときは，$k' = -k$ です．

終了条件を考える

「以降反射が起こらない状態」(終了状態と呼ぶことにします) とはどのようなときか考えます．

それは以下をいずれも満たすときです：

• 光線が進む向きの $x$ 成分が正
• 光線が 鏡 $\mathrm{S}$ に向かっているならば，光線の傾き $k$ が $t$ 以下
• 光線が 鏡 $\mathrm{T}$ に向かっているならば，光線の傾き $k$ が $0$ 以上

後者 $2$ つは簡単に判定できますが，$1$ つ目は少々難しいです．

実は、反射光の傾きから進行方向の $x$ 成分の符号を求めることができます．

• 光線が 鏡 $\mathrm{S}$ に向かっているとき：
  • $k < t$ のとき，負
  • $k = t$ のとき，平行 (終了状態に含まれる)
  • $k > t$ のとき，正
• 光線が 鏡 $\mathrm{T}$ に向かっているとき：
  • $k < 0$ のとき，正
  • $k = 0$ のとき，平行 (終了状態に含まれる)
  • $k > 0$ のとき，負

これらも，座標平面上での鏡と光線との様子を考えると分かります．

また，終了状態に初めて達したとき，「進行方向の $x$ 成分の符号が入れ替わった」と判定されることも分かります．

最初の反射から終了状態までに，ちょうど $1$ 回だけ進行方向の $x$ 成分の符号が反転するので，先ほどの式によって「進行方向の $x$ 成分の符号が反転した」と $2$ 回目に判定されたとき，光線ははじめて終了状態に達しています．(前者 $2$ つの条件(傾きに関する条件)も満たされています．)

これをシミュレーションすればよいですが，上述の議論における各式の分母が $0$ になる場合など，少々面倒な場合分けを行う必要があります．
詳細は実装例も参照してください．

---

なお，反射角を考える で得た $\alpha + \beta = 2 \theta$ という関係を用いてシミュレーションを行うこともできます．
こちらの実装は軽めです．

反射光を直線に展開して考える解法

この図のように反射光は直進すると考えます．

$\theta = \arctan(\frac{P}{Q})$ とします．
図中の青色の点線の方程式は $y = \tan(k\theta) \scriptsize \; (k = 2, 3, 4, \ldots)$ です．

すると，反射が起こる点と，図中の橙の線と青の線との交点 とが一対一に対応することが分かります．

したがって，直線 $y = 1$ と $y = \tan(k \theta) \scriptsize \; (k = 1, 2, 3, \ldots \land \; \scriptsize k \theta < \pi)$ との交点の個数を数えればよいです．

また，これは $k\theta < \pi$ なる正の整数 $k$ の個数に等しいですから，結局以下の値が答えに一致します：

• $\displaystyle \left\lceil \frac{\pi}{\theta} \right\rceil - 1 = \displaystyle \left\lceil \frac{\pi}{\arctan(\frac{P}{Q})} \right\rceil - 1$

解説：uni_kakurenbo

実装例