p8000题解

· · 题解

题解（circle）

考虑我们对 a 点集求一个凸包；

然后我们对这个凸包做一次旋转卡壳：

如果某次旋转卡壳经过了 \ge 4 个点，那么必定存在连线重合或平行；

根据这条线点数可以求出 z；

再根据两点距离，我们就可以找出对应的 x；

然后拿个 map 维护一下，看看一个点 +(-x) 的地方有没有点，没有则说明这个点 \in b；

然后输出就可以了。

时间复杂度 O(n \log n)

所有点在一条直线上的情况需要分类讨论特判一下。