We can use the binary search to find the answer. In each iteration, we solve the following subproblem:

There are $N$ lines on the two-dimensional plane. How many of the intersection points of two of these liens is in $x^2+y^2=r^2$?

The upper bound of the solution is required for the binary search. The solution of

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

is \(x=\frac{bf-ce}{ae-bd},y=\frac{cd-af}{ae-bd}\). Since \(|bf-ce|,|cd-af| \le 2 \times 10^6,|ae-bd| \ge 1\), the solution is at most \(2\sqrt 2 \times 10^6\).

Now we consider the subproblem.

Find the intersections of \(x^2+y^2=r^2\) and \(ax+by+c=0\) for each lien and sort them by the azimuth, then the subproblem is equivalent to:

There are a circle on the two-dimensional plane. You are given some segments whose endpoints are on the circle. Find the number of intersections of these segments.

We may cut the circle at some point to rephrase the problem as follows:

You are given $N$ segments, the $i$-th of which is $[ L_i,R_i ]$. Find the number of pairs $(i,j)$ such that $1 \le i,j \le N$ and $L_i < L_j < R_i < R_j$.

This problem can be solved as follows.

• Maintain an array of length $\max R$, each element initialized with $0$.
• Sort the segments in ascending order of $R_i$. Process each of them in the sorted order:
• Add the $L_i$-th value of the array to the answer.
• Add $+1$ to the $(L_i+1)$-th through $(R_i-1)$-th elements of the array.

The operations above can be done in a total of \(\mathrm{O}(N\log N)\) time.

Therefore, the problem has been solved in a total of \(\mathrm{O}(N\log N \log P)\) time, where \(P\) is the precision.