自动搬运

查看原文

来自洛谷，原作者为

	zhoutb2333 **

搬运于2025-08-24 22:09:03，当前版本为作者最后更新于2019-04-10 15:07:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这种做法基于这个事实：平面上 $n$ 个不重点组成的等腰三角形个数是 $O(n^{2.137})$ 级别的（证明在这里）

那也就是说我们可以枚举一个点为极点，然后把所有点按照离极点的距离排序，然后离极点距离相同的点分成一组。我们如果枚举组内点对的话，是不会 $O(n^3)$ 的。

这样的话这个题就比较简单了：我们先枚举每个点作为 $A$ 点，然后枚举组内点对，进而求出每个 $BC$ 线段左面、右面的 $A$ 点个数。

然后我们再枚举每个点作为 $D$ 点，继续枚举组内点对 $(B, C)$ ，然后把直线 $AD$ 插入极角序排序（所有合法的 $A$ 都在 $BC$ 的中垂线上）。最后再枚举组内点对 $(E, F)$ ，合法的直线 $AD$ 的极角范围是一个区间，二分即可。

复杂度是 $O(n^2 \log n +n^{2.137})$ （好玄学

代码在这里