首先考虑把定点置换到原点,则直线方程变为 \(y + y_0 = \dfrac a{1000}(x + x_0) + \dfrac b{1000}\)。
令 \(k = \dfrac a{1000}, c = \dfrac{ax_0 + b}{1000} - y_0\),则有 \(y = kx + c\)。
考虑二分答案,找到一个最小的圆,使得圆内有至少 \(m\) 个交点,圆的半径 \(r\) 就是答案。
在圆内,每条直线就化为了弦,两条弦相交等价于它们所对的优弧相交,可以求出交点后做极角排序来把弦的端点离散化,这样弦就转化为了数轴上的线段,于是问题转化为数轴上有多少对相交线段,扫描线 + 树状数组就能解决。
具体来说,会产生贡献的两条线段 \(i, j\) 满足 \(l_i \le l_j \le r_i \le r_j\),我们把线段按 \(l\) 排序,然后再用树状数组处理剩下的 \(r\) 的偏序问题就好。
算贡献的时间复杂度是 \(\mathcal O(n \log n)\)。
最后推交点:
\[\begin{cases}{} y = kx + c \\ x^2 + y^2 = r^2 \end{cases} \]把上面的 \(y\) 带到下面,整理一下就有 \((k ^ 2 + 1)x^2 + 2kcx + c^2 - r^2 = 0\)。
然后用笨蛋求根公式:
\[\Delta = 4k^2c^2 - 4(k^2 + 1)(c^2 - r^2) = 4(k^2r^2 + r^2 - c^2) \]当 \(\Delta \ge 0\),也即 \(k^2r^2 + r^2 - c^2 \ge 0\) 时,直线与圆有交点,此时解得
\[x = \dfrac{-kc \pm \sqrt{k^2r^2 + r^2 - c^2}}{k^2 + 1} \]再带回就能解 \(y\),也就解出了直线和圆的所有交点。
以上(找最小圆)的时间复杂度是 \(\mathcal O(n \log n \log V)\)。
接下来考虑如何计算答案。
把所有的合法交点分两类:恰在圆上的和圆内的。
- 恰在圆上的距离就是半径了,直接加就好。
- 对于在圆内的点,因为只有 \(\mathcal O(m)\) 个交点,所以直接开个 set 存前面线段的信息,暴力算交点求距离就好。
这样统计答案的时间复杂度就是 \(\mathcal O(m \log n)\)。
时间复杂度 \(\mathcal O(n \log n \log V + m \log n)\)。
简单算算就能发现极限数据下 \(m \log n \gg n \log n \log V\),耗时上计算答案占了大头,倒是前面找最小圆对耗时没啥影响,所以为了保证精度,多做几次二分罢~
标签:log,dfrac,Sum,Cross,圆内,交点,mathcal,线段,CF607E From: https://www.cnblogs.com/chy12321/p/17968470