CF607E Cross Sum

题意：给出平面上的 条直线，定义可重点集 包含所有直线两两的交点。如果某个点作为交点出现了多次，其在 中也会出现多次。

给出询问点 ，定义 为 中各个点到 的距离，求 中前 大的元素和。

，，时限 。

---

为了方便，将坐标系平移使得 恰为原点。

设 中第 大的元素的值为 ，可以看作这些交点都在一个圆心为原点，半径为 的圆内。

考虑如何求出 。二分后转化为判定问题，将每条直线截取在圆内的部分，问题变为若干弦的交点个数。

若两个弦交叉则恰产生一个交点。弦 交叉的充要条件是 或 ，为二维偏序的形式，不难 求解。

这一部分复杂度为 。

接下来要找出圆内的 个交点，即找出每个二维偏序。

用 std::set 维护，二分并遍历即可。复杂度为 。

注意，可能有多个点恰好在圆上。我们不妨先不算恰好在圆上的点，最后再按照个数加入，其贡献总是半径 。

（圆上的点可能非常多，所以必须不算，否则复杂度有问题）