Google Code Jam の2015年の Round 1A のC問題で、格子点との角度を求めて計算をする必要があるような問題がでました。また、他にも格子点が出てきて角度を計算して処理したくなる問題があります。

格子点同士を結んだ任意の二直線の角度差の最小値がわからなかったので考えた結果の覚え書きです。ウェブで探せば既にどこかにありそうな気もしますがまあ。

大きさが l*l になるような格子で格子点を結んだ場合、二つの直線のベクトルをそれぞれ (x₁, y₁), (x₂, y₂) とします。

それぞれは 0 から l までです。

この二つの傾きはそれぞれ y_i / x_i となるので、この二つの傾きの差は

(y₁x₂ – x₁y₂) / (x₁x₂)

となります。格子点なので分子は必ず整数なので、傾きの差は最小でも l^-2 となります。

また、逆数の差も必ず l^-2 あるので、絶対値の差だけでなく相対的な差も l^-2 以上あることになります。

ここで x₁ = x₂ = l の時、分子がlの倍数になってしまい 1/l より大きくなるので、実は l^-2 よりほんのすこし大きくなります。二直線が (l-1, 1) (l, 1) の時、 1 / l(l-1) で最小です。通常その差は意識しないので、以後は l^-2 として行きます。

角度差の最小値については、 0から45度（π/4）までを対象に考えます（他の領域でも計算過程が異なるだけで結果は同じになるはずなので）。

d/dx tan^-1x = cos² (tan^-1 x) はこの範囲で 1/2 から 1 までの範囲で変化するので、角度の差の最小値は l^-2/2 ラジアン、あるいは 90π^-1l^-2 度ということになります。

従って、計算するのに型を決定したりするにあたっては

傾きの計算と結果： 相対誤差または絶対誤差のうち小さい方が l^-2
ラジアンの保存：　絶対誤差が l^-2/2
ラジアンについてのEPSの設定：　l^-2/2 未満

実際には誤差が累積するので、これに対して余裕を持った値ということでしょうか。

なお、doubleは仮数部が52ビットらしいので、20ビットだとラジアンについても累積して41ビットにならなければよいので格子サイズの縦や横が20ビットくらいまで（1e6くらいまで）なら心配する必要はないという感じでしょうか。

変な組み合わせですごく小さな誤差が出るのでは？というのが怖かったのですが、これで安心して書けそうです。