[ABC263Ex] Intersection 2 题解

· · 题解

我们可以使用二进制搜索来找到答案.在每次迭代中,我们解决以下子问题:

二维平面上有N行.其中两个留置权的交点有多少在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|≤2×10^6,|ae-bd|≥1,解决方案最多是\sqrt[2]{2} \times 10^6

现在我们考虑子问题.

找到每个连线的x^2+y^2=r^2和ax+by+c=0的交集，并按方位角排序，则子问题等价于：

在二维平面上有一个圆.给您一些端点位于圆上的线段.求出这些线段的交点数.

我们可以在某个点上切割圆圈,将问题重新表述如下:

给您N段,第i段是[L_i,R_i].找到对(i,j)的数量,使1≤i,j≤N和L_i<L_j<R_i<R_j.

这个问题可以通过以下方式解决.

  • 维护一个长度为\max R的数组，每个元素初始化为0.
  • 按R_i的升序对段进行排序.按排序顺序处理每个段:
    • 将数组的L_i值添加到答案中.
    • 将+1添加到第(L_i+1)到(R_i-1)数组的第几个元素

时间复杂度O(N \log N)

时间总复杂度O(N \log N \log P),其中P是精度.