[DS记录]BZOJ2961: 共点圆(+4140: 共点圆加强版)

· · 个人记录

题意:

圆并不好处理,咱也不会圆的反演,而且听说严重掉精度……

题目给出了过原点的奇怪条件,我们还是先推推式子。

(a,b)\ in\ \circ\!(c,d)\Rightarrow (a-c)^2+(b-d)^2\leq c^2+d^2 \Rightarrow a^2-2ac+b^2-2bd\leq 0\Rightarrow a^2+b^2\leq 2ac+2bd \Rightarrow \frac{a^2+b^2}{2b}\leq c·\frac{a}{b}+d

这个判据可以看做 : 点(\frac{a^2+b^2}{2b},\frac{a}{b})是否在直线y=cx+d下方

可能会有b=0或者a=0,等会到OJ上交互看一看再决定要不要讨论。

现在问题就变成了:

考虑静态的问题,我们可以先排序再单队建立凸包。

对所有询问按照x排序,然后根据单调性依次在凸包上爬,不计排序总复杂度为O(n)

现在要变成动态,没有说强制在线,加一个CDQ分治就好了。

注意在CDQ中使用归并,复杂度O(nlogn)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

现在考虑加强版 : 强制在线。

写一个二进制分组同时维护O(logn)个凸包就好了。

查询不能批量做了,在这些凸包上二分即可。

复杂度O(nlog^2n)