之前觉得不可做的一道题.然后昨天听mhy一句话瞬间懂:几何反演.然后mhy说这题用cdq?骗我读书少呢?
html写公式好郁闷.把设圆心是(p,q),点是(x,y),那么点在圆内的条件是
(p-x)2+(q-y)2 ≤ p2+q2
转化一下变成
q ≥ -(x/y) * p + (x2+y2) / (y*2)
然后就可以把(p,q)看作一个点,每个询问就是询问之前的所有点是否都在这条直线的上方.
那么直接归并排序喽.处理出左边的凸壳再单调扫一遍右边的所有直线.这样复杂度是O(n*logn),又短又快yeah.
然后还听说有精度误差?我全程double没用eps也没出事啊hhh