二分探索を行うことにより、この問題は以下の問題を何回か解くことにより解を得ることができます。

$2$ 次元平面上に $N$ 本の直線があります。$2$ 本の直線の交点のうち、$x^2+y^2=r^2$ の内部にあるものの個数を求めてください。

二分探索のために、解の最大値を考える必要があります。

\(\begin{cases} ax+by+c=0\\ dx+ey+f=0 \end{cases}\)

の解は \(x=\frac{bf-ce}{ae-bd},y=\frac{cd-af}{ae-bd}\) です。\(|bf-ce|,|cd-af| \le 2 \times 10^6,|ae-bd| \ge 1\) より 解は高々 \(2\sqrt 2 \times 10^6\) であることがわかります。

以降、二分探索後の問題を考えることとします。

\(x^2+y^2=r^2\) と \(ax+by+c=0\) の交点を求め、偏角ソートを行うことにより上記の問題は以下の問題と同じものとなります。

$2$ 次元平面上に円があります。円上の $2$ 点を端点とする線分がいくつか与えられます。 $2$ 本の線分の交点の個数を求めてください。

また、円をどこか \(1\) 箇所で切断してもいいため、この問題は更に以下の問題に言い換えられます。

$N$ 個の区間が与えられます。$i$ 個目の区間は $[ L_i,R_i ]$ です。 $1 \le i,j \le N$ かつ $L_i < L_j < R_i < R_j$ を満たす整数の組 $(i,j)$ の個数を求めてください。

この問題は以下のようにして解くことができます。

• 長さが $\max R$ の配列を持つ。始め全要素は $0$ とする。
• 区間を $R_i$ の昇順にソートする。ソートした順に以下の操作を行う。
• 配列の $L_i$ 番目の値を解に加える。
• 配列の $L_i+1$ 番目から $R_i-1$ 番目の値に $+1$ する。

上記の操作は BIT や双対セグ木、遅延セグ木を用いて \(\mathrm{O}(N\log N)\) で行うことができます。

より、この問題を精度を \(P\) として \(\mathrm{O}(N\log N \log P)\) で解くことができました。