• 前者は実装を楽にするためです。後者は誤差の評価を楽にするためです。
• 実装を簡単にするためです。これを行うと、原点からその直線へ下ろした垂線（存在すれば）の足が \((kA,kB)\ (k>0)\) の形になり、その偏角を \(\tan^{-1}\dfrac{B}{A}\) などで計算できます.
• 実装を簡単にし、誤差の評価を楽にするためです。円と直線の交点を出してそれらを偏角ソートする場合、同様の三角関数の計算を使ったり、円と直線の交点を二次方程式を解いたりしますが、誤差を抑えるのが面倒な計算を経ることになると考えたためです。この方針でなくても根気よく計算することで本ユーザ解説とおおよそ同じ程度のオーダーの誤差評価ができると思います。
  • 誤差の評価を楽にするためでしたが、楽になったかは不明です。同様にこの方針でなくてもがんばって計算することで本ユーザ解説とおおよそ同じ程度のオーダーの誤差評価ができると思います。
• 誤差の評価を楽にするためです。\(r^2\) の真の値が double で正確に表現できるようにしておくことで、円と直線が共有点を持つかを正確に判定することができます。そうでないと、円と直線の位置関係を間違えて判定してしまう場合があり場合分けが増えて困ると考えたためです。この方針でなくても本ユーザ解説とおおよそ同じ程度のオーダーの誤差評価ができると思いますが、どう議論をすればいいのかあまりわかりません。
• 定数倍高速化のためです。解の絶対値が \(1\) 以下であれば絶対誤差を、\(1\) 以上であれば相対誤差を小さくするように動くことで少ない回数の反復で所望の誤差の範囲の値を得ることができます。

直線が円と交点を持つかは、\(\dfrac{|C|}{\sqrt{A^2+B^2}}\leq \sqrt{r^2}\iff0\leq-C^2+r^2\left(A^2+B^2\right)\) で求められます。 \(C^2,A^2+B^2\) はいずれも double で正確に表すことができる整数です。 r_sq に \(r^2\) の正確な値が入っているなら、\(0\leq-C^2+r^2\left(A^2+B^2\right)\) が成り立つとき、かつそのときに限りfma(r_sq, A * A + B * B, -C * C) の符号が \(+\) になります。 よって、直線が円の内部にあるかの判定に失敗することはありません。

偏角ソートに成功すると、それ以降は円と直線の交点の偏角の大小関係のみで数え上げの結果が決まります。 これはすべて整数の範囲で計算を行うことができるため、誤差によって計算結果が変わることはありません。

        const auto d{sqrt(A * A + B * B)};
        if(B > 0){
            if(-B < A && A < B){
                const auto cos_theta{A / d};
                theta = pi_half - asin(cos_theta);
            }else{
                const auto sin_theta{B / d};
                theta = A > 0 ? asin(sin_theta) : pi - asin(sin_theta);
            }
        }else{
            if(B < A && A < -B){
                const auto cos_theta{A / d};
                theta = pi_triple_half + asin(cos_theta);
            }else{
                const auto sin_theta{B / d};
                theta = A > 0 ? pi_2 + asin(sin_theta) : pi - asin(sin_theta);
            }
        }

if 文および条件演算子の条件はすべて整数の比較なので、誤差はありません。

d は、double で正確に表せる値 \(A^2+B^2\) の平方根を double に丸めたものなので、たかだか \(0.5\operatorname{ulp}\) の誤差があります。よって、d は \(\left[\sqrt{A^2+B^2}\left(1-2^{-53}\right),\sqrt{A^2+B^2}\left(1+2^{-53}\right)\right]\) に存在します。

cos_theta は double で正確に表せる値 \(A\) を d で割った正確な値を double に丸めたものです。 この計算において、割り算の丸めでたかだか \(0.5\operatorname{ulp}\) の誤差が生じます。 \(A=0\) のとき、cos_theta も \(0\) になります。 \(A\neq0\) のとき、\(|\cos_{\operatorname{theta}}|>\dfrac{1}{\sqrt{10^6+1}}\) です。 なので、割り算の丸めではたかだか \(2^{-53}\) の相対誤差が生じます。 よって、cos_theta の \(\cos_{\operatorname{theta}}\) との相対誤差はたかだか \(\dfrac{2}{2^{53}-1}\) です。

sin_theta はまったく同様にして真の値からの相対誤差が高々 \(\dfrac{2}{2^{53}-1}\) であることが言えます。

if 文の条件から、\(-\dfrac{1}{\sqrt{2}}\leq\operatorname{sin_{theta}},\operatorname{cos_{theta}}\leq\dfrac{1}{\sqrt{2}}\) であって、これらを \(\sin^{-1}\) した結果の真の値は \(\left[-\dfrac{\pi}{4},\dfrac{\pi}{4}\right]\) にあることがわかります。また、\(x\in[-1,1]\) に対して \(|x|\leq|\sin^{-1}x|\) であるので、\(|\sin^{-1}\operatorname{sin_{theta}}|,|\sin^{-1}\operatorname{cos_{theta}}|\) は \(0\) でなければ \(\dfrac{1}{\sqrt{10^6+1}}\) 以上です。

これらから、asin(cos_theta) および asin(sin_theta) の値と真の値との絶対誤差は高々 \(\dfrac{1}{2^{51}}\) 以下であることが言えます。

\(0\lt B\lt A\) のとき、\(\theta=\sin^{-1}\operatorname{sin_{theta}}\) です。 これは上で求めた通り、絶対誤差は高々 \(\dfrac{1}{2^{51}}\) 以下です。
そうでないとき、\(\theta=\dfrac{k}{2}\pi\pm\sin^{-1}\alpha\ (k=1,2,3\wedge\alpha=\operatorname{sin_{theta}},\operatorname{cos_{theta}})\) と表されます。 加減算でたかだか \(1\) 回丸めが行われ、たかだか \(0.5\operatorname{ulp}\) の誤差が発生します。 \(0.5\operatorname{ulp}\) は、pi_2 などと asin(sin_theta) などとの和の真の値が \(2\pi+\dfrac{13}{2^{54}}\) 以下であるため、たかだか \(\dfrac{1}{2^{51}}\) です。 よって、計算結果の \(\theta\) との絶対誤差はたかだか \(\dfrac{21}{2^{54}}\) です。

この部分は \(4\times10^6\) 通り程度の入力しかないので、全探索を用いて評価を行うことができます。 実際に計算を行うと、最悪の場合 \(16.59\times2^{-54}\) 程度の絶対誤差が生じていることが確認できます。（誤差が最大になるときは \((A,B)=(786,-767)\) のとき、真の値 \(5.51002091848314726693722961\ldots\) に対し、計算結果は \(5.51002091848314634603411832\ldots\) です。）

            const real phi{0 <= copysign(1, fma(r_sq, A * A + B * B, -2 * C * C)) ? pi_half - asin(sqrt(C * C / r_sq / (A * A + B * B))) : asin(sqrt(1 - C * C / r_sq / (A * A + B * B)))};

if 文で書き直すと以下のようになります。

            real phi;
            if(0 <= copysign(1, fma(r_sq, A * A + B * B, -2 * C * C))){
                phi = pi_half - asin(sqrt(C * C / r_sq / (A * A + B * B)));
            }else{
                phi = asin(sqrt(1 - C * C / r_sq / (A * A + B * B)));
            }

条件分岐では \(\dfrac{|C|}{\sqrt{A^2+B^2}}\leq\dfrac{\sqrt{r^2}}{\sqrt{2}}\) であるか（\(\iff\dfrac{\pi}{4}\leq\varphi\leq\dfrac{\pi}{2}\) であるか）を正確に判定しています。

\(\dfrac{\pi}{4}\leq\varphi\leq\dfrac{\pi}{2}\) のとき、 \(\tan^{-1}\dfrac{B}{A}\) の評価と同様にして \(e_\varphi(\varphi)=\dfrac{41}{2^{56}}\) とできることが示せます。

\(\varphi=0\) のとき、phi も \(0\) です。よって、\(e_\varphi(0)=0\) です。

\(0<\varphi<\dfrac{\pi}{4}\) のとき、\(\varphi=\sin^{-1}\sqrt{1-\dfrac{C^2}{r^2\left(A^2+B^2\right)}}\) を用いて phi を計算しています。 このとき、 \(\dfrac{C^2}{r^2\left(A^2+B^2\right)}=1-\sin^2\varphi\) です。 C * C / r_sq は条件より \(\dfrac{A^2+B^2}{2}\) 以上 \(A^2+B^2\) 以下で、double で正確に表せる値 \(C^2\) と \(r^2\) の商を double に丸めたものです。 よって、C * C / r_sq にはたかだか \(2^{-53}\) の相対誤差があります。 C * C / r_sq / (A * A + B * B) はこれを double で正確に表せる値 \(A^2+B^2\) で割ったものを double に丸めたもので、\(\dfrac{1}{2}\) 以上 \(1\) 以下です。 よってこの丸めでもたかだか \(2^{-53}\) の相対誤差が生じるため、C * C / r_sq / (A * A + B * B) は \(\left[\left(1-\sin^2\varphi\right)\left(1-2^{-52}+2^{-106}\right),\left(1-\sin^2\varphi\right)\left(1+2^{-52}+2^{-106}\right)\right]\cap\left[\dfrac{1}{2},1\right]\) に存在します。

1 - C * C / r_sq / (A * A + B * B) は、\(\left[0,\dfrac{1}{2}\right]\) に存在します。 なので計算結果の丸め誤差は生じず、この計算結果は \(\left[1-\left(1-\sin^2\varphi\right)\left(1+2^{-52}+2^{-106}\right),1-\left(1-\sin^2\varphi\right)\left(1-2^{-52}+2^{-106}\right)\right]\cap\left[0,\dfrac{1}{2}\right]\) に存在します。

これを整理します。\[\begin{aligned}1-\left(1-\sin^2\varphi\right)\left(1+2^{-52}+2^{-106}\right)&=\sin^2\varphi\left(1+2^{-52}+2^{-106}-\dfrac{2^{-52}+2^{-106}}{\sin^2\varphi}\right)\\&\geq\sin^2\varphi\left(1-\dfrac{2^{-52}+2^{-106}}{\sin^2\varphi}\right)\end{aligned}\] が成り立ちます（\(0\lt\varphi\lt\dfrac{\pi}{4}\) より \(\sin^2\varphi\gt0\) です）。同様に \(1-\left(1-\sin^2\varphi\right)\left(1-2^{-52}+2^{-106}\right)\geq\sin^2\varphi\left(1+\dfrac{2^{-52}-2^{-106}}{\sin^2\varphi}\right)\) が成り立つので、1 - C * C / r_sq / (A * A + B * B) の計算結果は \[\left[\sin^2\varphi\left(1-\dfrac{2^{-52}+2^{-106}}{\sin^2\varphi}\right),\sin^2\varphi\left(1+\dfrac{2^{-52}-2^{-106}}{\sin^2\varphi}\right)\right]\cap\left[0,\dfrac{1}{2}\right]\] に存在します。

この区間に含まれる値の平方根を含むような区間について考えます。 \(\left[\sqrt{1-x},\sqrt{1+x}\right]\subseteq\left[1-x,1+\dfrac{x}{2}\right]\ (0\leq x\leq1)\) と \(\left[\sqrt{a-b},\sqrt{a+b}\right]\subseteq\left[\sqrt{\vphantom{h}a}-\sqrt{b},\sqrt{\vphantom{h}a}+\sqrt{b}\right]\ (0\leq b\leq a)\) を用いると、 \[\begin{aligned}&\left[\sin\varphi\left(1-\dfrac{2^{-52}+2^{-106}}{\sin^2\varphi}\right),\sin\varphi\left(1+\dfrac{2^{-53}-2^{-107}}{\sin^2\varphi}\right)\right]\cap\left[\sin\varphi-\sqrt{2^{-52}+2^{-106}},\sin\varphi+\sqrt{2^{-52}-2^{-106}}\right]\cap\left[0,\dfrac1{\sqrt2}\right]\\ \subseteq&\left[\sin\varphi\left(1-\dfrac{2^{-52}+2^{-106}}{\sin^2\varphi}\right),\sin\varphi\left(1+\dfrac{2^{-53}-2^{-107}}{\sin^2\varphi}\right)\right]\cap\left[\sin\varphi-2^{-26}-2^{-81},\sin\varphi+2^{-26}-2^{-81}\right]\cap\left[0,\dfrac1{\sqrt2}\right]\end{aligned}\] はそのような区間であることがわかります。 平方根の計算において、丸めによる絶対誤差はたかだか \(2^{-54}\) なので、sqrt(1 - C * C / r_sq / (A * A + B * B)) は \[\begin{aligned}&\left[\sin\varphi\left(1-\dfrac{2^{-52}+2^{-106}}{\sin^2\varphi}\right)-2^{-54},\sin\varphi\left(1+\dfrac{2^{-53}-2^{-107}}{\sin^2\varphi}\right)+2^{-54}\right]\cap\left[\sin\varphi-2^{-26}-2^{-54}-2^{-81},\sin\varphi+2^{-26}+2^{-54}-2^{-81}\right]\cap\left[0,\dfrac1{\sqrt2}+2^{-54}\right]\\ \subseteq&\left[\sin\varphi-\dfrac{2^{-52}+2^{-54.5}+2^{-106}}{\sin\varphi},\sin\varphi+\dfrac{2^{-53}+2^{-54.5}-2^{-107}}{\sin\varphi}\right]\cap\left[\sin\varphi-2^{-26}-2^{-54}-2^{-81},\sin\varphi+2^{-26}+2^{-54}-2^{-81}\right]\cap\left[0,\dfrac1{\sqrt2}+2^{-54}\right]\\ =&\left[\sin\varphi-\delta_0,\sin\varphi+\delta_1\right]\cap\left[\sin\varphi-\delta_2,\sin\varphi+\delta_3\right]\cap\left[0,\dfrac1{\sqrt2}+2^{-54}\right]\eqqcolon I\end{aligned}\] に存在することがわかります（\(\dfrac{1}{\sqrt{2}}\) は double で正確に表せない値なので、\(\dfrac{1}{\sqrt{2}}\) 以下の値は double で表せる \(\dfrac{1}{\sqrt{2}}\) に最も近い値 \(\dfrac{6369051672525773}{2^{53}}\) 以下へ丸められ、これは \(\dfrac{1}{\sqrt{2}}+2^{-54}\) 以下です）。

\(0\leq\varepsilon,|x|\leq\dfrac{1}{\sqrt2},|x+\varepsilon|\leq\dfrac{4}{5}\) において \[\left[\sin^{-1}(x-\varepsilon),\sin^{-1}x\right]\subseteq\left[\sin^{-1}x-\dfrac{5}{3}\varepsilon,\sin^{-1}x\right],\left[\sin^{-1}x,\sin^{-1}(x+\varepsilon)\right]\subseteq\left[\sin^{-1}x,\sin^{-1}x+\dfrac{5}{3}\varepsilon\right]\] が成立することを用います。 \(J\coloneqq\left\{\sin^{-1}x\middle|x\in I\right\}\) を評価します。

\(I\subseteq\left[0,\dfrac{1}{\sqrt{2}}+2^{-54}\right]\) と \(\sin^{-1}\) が単調増加関数であることからただちに \(J\subseteq\left[0,\sin^{-1}\left(\dfrac{1}{\sqrt{2}}+2^{-54}\right)\right]\) が言えます。
\(I\) を \(\left[\sin\varphi-\varepsilon_0,\sin\varphi+\varepsilon_1\right]\ (\varepsilon_0,\varepsilon_1\geq0)\) と表すとき、\(I\subseteq\left[0,\dfrac{1}{\sqrt{2}}+2^{-54}\right]\) なので \(\varepsilon_0\leq\sin\varphi,\varepsilon_1\leq\dfrac{1}{\sqrt{2}}+2^{-54}-\sin\varphi\) です。 よって、上の条件 \(0\leq\varepsilon,|x|\leq\dfrac{1}{\sqrt2},|x+\varepsilon|\leq\dfrac{4}{5}\) を満たすので \(J\subseteq\left[\varphi-\dfrac{5}{3}\varepsilon_0,\varphi+\dfrac{5}{3}\varepsilon_1\right]\) です。 また、\(I\subseteq\left[\sin\varphi-\delta_0,\sin\varphi+\delta_1\right]\) が成り立つので、\(\varepsilon_0\leq\delta_0,\varepsilon_1\leq\delta_1\) です。 よって、\(J\subseteq\left[\varphi-\dfrac{5}{3}\varepsilon_0,\varphi+\dfrac{5}{3}\varepsilon_1\right]\subseteq\left[\varphi-\dfrac{5}{3}\delta_0,\varphi+\dfrac{5}{3}\delta_1\right]\) です。まったく同様にして \(J\subseteq\left[\varphi-\dfrac{5}{3}\delta_2,\varphi+\dfrac{5}{3}\delta_3\right]\) です。
よって、\(J\subseteq\left[\varphi-\dfrac{5}{3}\delta_0,\varphi+\dfrac{5}{3}\delta_1\right]\cap\left[\varphi-\dfrac{5}{3}\delta_2,\varphi+\dfrac{5}{3}\delta_3\right]\cap\left[0,\sin^{-1}\left(\dfrac{1}{\sqrt{2}}+2^{-54}\right)\right]\) です。

\(J\) の要素は大きくても \(\sin^{-1}\left(\dfrac{1}{\sqrt{2}}+2^{-54}\right)\simeq\dfrac{\pi}{4}+2^{-54}\sqrt{2}\lt1\) であるため、 asin の計算にかかる誤差がたかだか \(1\operatorname{ulp}\) であるとすると、計算結果とその真の値との絶対誤差はたかだか \(2^{-53}\) です。

また、 double で表現可能な \(\dfrac{1}{\sqrt2}\) 以上の最小の値 \(\dfrac{6369051672525773}{2^{53}}\) を逆正接関数に与えたもの以上の double で表現可能な最小の数 \(\dfrac{7074237752028441}{2^{53}}\)が \(\dfrac{\pi}{4}+2^{-53}\) 以下であることから、phi は \(\left[0,\dfrac{\pi}{4}+2^{-53}\right]\) に存在します。

よって、phi は \(\left[\varphi-\dfrac{5}{3}\delta_0-2^{-53},\varphi+\dfrac{5}{3}\delta_1+2^{-53}\right]\cap\left[\varphi-\dfrac{5}{3}\delta_2-2^{-53},\varphi+\dfrac{5}{3}\delta_3+2^{-53}\right]\cap\left[0,\dfrac{\pi}{4}+2^{-53}\right]\) に存在します。

\(\dfrac53\delta_0+2^{-53},\dfrac53\delta_1+2^{-53},\dfrac53\delta_2+2^{-53},\dfrac53\delta_3+2^{-53}\) を上から評価します。\(\sin\varphi\in\left[0,\dfrac1{\sqrt2}\right]\) なので、 \[\begin{aligned} \dfrac53\delta_0+2^{-53}&=\dfrac53\dfrac{2^{-52}+2^{-54.5}+2^{-106}}{\sin\varphi}+2^{-53}&\qquad&\\ &=\dfrac1{\sin\varphi}\left(\dfrac532^{-52}+\dfrac532^{-54.5}+\dfrac532^{-106}\right)+\sqrt{2}\times2^{-53.5}&\qquad&\\ &\leq\dfrac1{\sin\varphi}\left(\dfrac532^{-52}+\dfrac532^{-54.5}+\dfrac532^{-106}\right)+\dfrac1{\sin\varphi}\times2^{-53.5}&&(\sin\varphi\leq\dfrac{1}{\sqrt{2}}\text{ より})\\ &\leq\dfrac{5}{\sin\varphi}\times2^{-53} \end{aligned}\] が成り立ちます。同様の計算を行うことで、\(\dfrac53\delta_1+2^{-53}\leq\dfrac3{\sin\varphi}\times2^{-53}\) が得られます。

また、\(\dfrac53\delta_3+2^{-53}=\dfrac53\left(2^{-26}+2^{-54}+2^{-81}\right)+2^{-53}\leq2^{-25},\dfrac53\delta_4+2^{-53}=\dfrac53\left(2^{-26}+2^{-54}-2^{-81}\right)+2^{-53}\leq2^{-25}\) が成り立ちます。

よって、\(0\lt\varphi\lt\dfrac\pi4\) において、\(e_\varphi(\varphi)=\min\left\{\dfrac{5}{\sin\varphi}\times2^{-53},2^{-25}\right\}\) とすることができます。

得られている誤差の評価は回転によって不変であるので、適当に全体を回転させることで \(\theta_0=0\) としてよいです。 対称性から、\(\varphi_0\geq\varphi_1\) として一般性を失いません。 対称性から、\(|(\theta_0+\varphi_0)-(\theta_1+\varphi_1)|\leq e(\varphi_0)+e(\varphi_1)\) もしくは \(|(\theta_0+\varphi_0)-(\theta_1-\varphi_1)|\leq e(\varphi_0)+e(\varphi_1)\) が成り立つとしてよいです。

今回の問題設定において、\(2\) 直線がなす角度は最小で \(\alpha=\tan^{-1}\dfrac1{1996002}\) です（\(\dfrac1{1996002}=\dfrac{999\times999-1000\times998}{1000\times999+999\times998}\)）。

よって、\(\varphi_0,\varphi_1\) を固定したとき、\(\theta_1\) が満たすべき条件は次のようになります。

• \(\alpha\leq\theta_1\leq\pi-\alpha\;\vee\;\pi+\alpha\leq\theta_1\leq2\pi-\alpha\)
• \(-e(\varphi_0)-e(\varphi_1)+\varphi_0-\varphi_1\leq\theta_1\leq e(\varphi_0)+e(\varphi_1)+\varphi_0-\varphi_1\;\vee\;-e(\varphi_0)-e(\varphi_1)+\varphi_0+\varphi_1\leq\theta_1\leq e(\varphi_0)+e(\varphi_1)+\varphi_0+\varphi_1\)

\(2\) つめの条件が満たされているとき、\(-\alpha\lt-2^{-24}-\dfrac{21}{2^{52}}\leq\theta_1\leq\pi+\dfrac{209}{2^{55}}\lt\pi+\alpha\) なので、\(1\) つめの条件は単に \(\alpha\leq\theta_1\leq\pi-\alpha\) となります。 また、\(2\) つめの条件の区間の長さはいずれもたかだか \(2^{-23}+\dfrac{21}{2^{51}}\) であるため、\(\theta_1\) が動ける範囲は \[\begin{aligned}S&=\left[a_0,a_1\right]\cup\left[a_2,a_3\right]\\&=\left[\max\{\alpha,-e(\varphi_0)-e(\varphi_1)+\varphi_0-\varphi_1\},e(\varphi_0)+e(\varphi_1)+\varphi_0-\varphi_1\right]\cup\left[-e(\varphi_0)-e(\varphi_1)+\varphi_0+\varphi_1,\min\{\pi-\alpha,e(\varphi_0)+e(\varphi_1)+\varphi_0+\varphi_1\}\right]\end{aligned}\] と書けます（便宜上 \(a>b\) のとき \(\left[a,b\right]=\varnothing\) とします）。

\(\cos^{-1}\dfrac{\cos\varphi_0}{\cos\varphi_1}\in S\) なら、\(2\) 直線の交点が原点と最も近いときは \(\theta_1=\cos^{-1}\dfrac{\cos\varphi_0}{\cos\varphi_1}\) のとき、その距離は \(\sqrt{r^2}\cos\varphi_1\) です。 \(\varphi_0-\varphi_1\leq\cos^{-1}\dfrac{\cos\varphi_0}{\cos\varphi_1}\leq\varphi_0\) なので、\(\cos^{-1}\dfrac{\cos\varphi_0}{\cos\varphi_1}\in S\iff\alpha\leq\cos^{-1}\dfrac{\cos\varphi_0}{\cos\varphi_1}\leq e(\varphi_0)+e(\varphi_1)+\varphi_0-\varphi_1\) です。

\(\cos^{-1}\dfrac{\cos\varphi_0}{\cos\varphi_1}\notin S\) なら、\(2\) 直線の交点の原点からの距離は \(\theta_1=a_0,a_1,a_2,a_3\) のいずれかにおいて最小・最大をとります。

それぞれ評価します。

判定部分は誤差なしで計算を行うことができます。

与えられた \(2\) 直線 \(l_0:A_0x+B_0y+C_0=0,l_1:A_1x+B_1y+C_1=0\ (C_0,C_1\leq0)\) に対して、半径 \(\sqrt{r^2}\) の円との交点 \(p_{00},p_{01},p_{10},p_{11}\) の位置関係が高速に得られればよいです。 ただし、\(l_0\) と円との交点を \(p_{00},p_{01}\)、\(l_1\) と円との交点を \(p_{10},p_{11}\) とし、\(l_0,l_1\) へ原点から下ろした垂線の足 \(h_0,h_1\) について \(p_{00},h_0,p_{01}\) および \(p_{10},h_1,p_{11}\) がこの順に時計回りにあるとします。

\(h_0:\left(-\dfrac{A_0C_0}{A_0^2+B_0^2},-\dfrac{B_0C_0}{A_0^2+B_0^2}\right),h_1:\left(-\dfrac{A_1C_1}{A_1^2+B_1^2},-\dfrac{B_1C_1}{A_1^2+B_1^2}\right)\) は偏角がこの順であるとして一般性を失いません。この確認は整数の範囲で可能です。

円内に交点があるかは、\(\dfrac{(A_0C_1-A_1C_0)^2+(B_0C_1-B_1C_0)^2}{(A_0B_1-A_1B_0)^2}\leq r^2\) かを判定すればよいです。 \((A_0B_1-A_1B_0)^2\) は \(2^{42}\) 以下、\((A_0C_1-A_1C_0)^2+(B_0C_1-B_1C_0)^2\) は \(2^{43}\) 以下の整数なので double で正確に表現できます。 よって、\(0\leq(A_0B_1-A_1B_0)^2\times r^2-\left((A_0C_1-A_1C_0)^2+(B_0C_1-B_1C_0)^2\right)\) かを判定すればよく、これは正確に判定できます。

そうでないとき、\(2\) 直線は円内に交点を持ちません。 このとき、直線どうしの位置関係は整数の範囲の計算のみで決定できます。

円周上の適当な点からはじめた順序にするため、弦がその点をまたぐか判定する必要がありますが、同様に double で正確に判定できます。

詳細はこの提出を確認してください。