P16522 自破碎的天空坠落

· · 题解

观察到 y=kx+b 这种形式就很根号分治。其中 k,x 满足当一个 >\sqrt{|y-b|} 时，另一个一定 \leq\sqrt{|y-b|}。阈值是 \sqrt{|y-b|}=200，对 k 或者 x 分治是不是一样的。

::::success[$1\leq k \leq 200] 直接枚举 k，对于每一组 x,y，得到 b=y-kx，存储每一组 {k,b}$ 的答案。
::::success[$ k >200] 这里 x \in [0,200]，可以对 x 预处理，存储每一组 {x,y}$ 的答案。

然后做到 O(nB)，取 B=200。