今回扱うのはyukicoder contest 470 D問題 No.3180 angles sumです。公式解説は$\tan$の加法定理や回転行列を用いて角度の一致判定をしていますが、複素数を用いるともっと軽い実装で処理できミスをしにくいのでその解説をしてみます。

問題の概要

正確な問題文はこちらです。

$xy$平面上の原点と異なる格子点$A,B,C$に対し、

\[ \textrm{arg}(A) + \textrm{arg}(B) = \textrm{arg}(C) \]

が成り立つか否かを判定してください。ただし$\textrm{arg}$は度数法の偏角を表し、$0 \leq \textrm{arg}(A), \textrm{arg}(B) \leq 90$かつ$0 \leq \textrm{arg}(C) \leq 180$を満たします。

前置き

高校指導要領はころころ変わっており、世代によっては行列を学ばないこともあります。そういう世代が$2$次元ベクトルの回転を扱う際にどうしているかと言うと、回転行列を使う代わりに複素平面を使います。

解説

格子点$A,B,C$の$xy$座標をそれぞれ$(A_X,A_Y),(B_X,B_Y),(C_X,C_Y)$と置きます。

虚数単位$i$を用いて複素数$\alpha,\beta,\gamma$をそれぞれ$A_X + A_Y i,B_X + B_Y i,C_X + C_Y i$と定めると、複素数乗算と偏角の関係から

\[ \textrm{arg}(\alpha) + \textrm{arg}(\beta) = \textrm{arg}(\alpha \beta) \]

であるので判定すべき式は

\[ \textrm{arg}(\alpha \beta) = \textrm{arg}(\gamma) \]

です。左辺の$\alpha \beta$は複素数乗算の定義から$(A_X B_X - A_Y B_Y) + (A_X B_Y + B_X A_Y)i$と表せ、問題の制約から64bit整数の範囲で処理できます。

結局実部と虚部が整数である２つの複素数の偏角比較の問題となりました。

これは実部（$\textrm{Re}$で表す）と虚部（$\textrm{Im}$で表す）の最大公約数で割って得られる複素数の一致で判定すれば良いです。つまりは$\alpha \beta$を$\delta$と置いて

\[ \frac{\delta}{\gcd(\textrm{Re}(\delta),\textrm{Im}(\delta))} = \frac{\gamma}{\textrm{gcd}(\textrm{Re}(\gamma),\textrm{Im}(\gamma))} \]

という等式を判定すれば良いです。最大公約数は約数でもあるので、この等式も整数の範囲で誤差なく処理できます。

この等式を判定する代わりに$\gamma,\delta$を$xy$平面に戻して外積を用いた平行判定をする手もありますが、$180$度のずれが出た時に誤判定をしないように注意して実装をする必要があります。

最大公約数を使うとユークリッドの互除法分の計算量がつきますが、細かい場合分けが不要になるので実装や考察のミスを減らしやすいという利点があります。（ユークリッドの互除法自体に正負の場合分けをミスする可能性はありますが、あらかじめライブラリー化してverifyしておきましょう）

実装例

• c++: https://yukicoder.me/submissions/1099346
• PyPy3: https://yukicoder.me/submissions/1099344
• cLay: https://yukicoder.me/submissions/1099341

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白は半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。