|
|
|
我们画图可以发现，如果两个线段相交，则每个线段的两个端点(在圆周上)所对应的劣弧极角区间一定相交,我们计算出这些极角区间，离散化，然后求出有多少对区间相交即可(需要使用线段树/树状数组/平衡树维护),时间复杂度为$\Large O(n\log_2n)$
连立方程, $\Large ax+by+c=0$ $\Large x^2+y^2=r^2$ 得 $\Large x=\frac {-ac\pm \sqrt {(ac)^2+(b^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$ $\Large y=\frac {-bc\pm \sqrt {(bc)^2+(a^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$ 然而，一些极角区间可能跨过了0度线,我们不妨称之为智障区间，比如[300,30],我们把这些区间记两次数，以[300,390]计算一次，[-60,30]计算一次，可以保证这两次智障区间和非智障区间相交的对只会被计算一次，然而智障区间和智障区间相交的对被计算了两次，再对所有的智障区间计算一次并减掉即可 |