自动搬运

查看原文

来自洛谷，原作者为

	€€£ 中国收钱协会(€hina€ounting£oundation)唯一官方认证账号，有事欢迎@（有时候可能不在）||https://www.luogu.com.cn/paste/hm8t61yq

搬运于2025-08-24 22:35:03，当前版本为作者最后更新于2021-12-28 18:38:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解（circle）

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

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

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

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

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

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

然后输出就可以了。

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

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