题解 P5286 【[HNOI2019]鱼】

· · 题解

这种做法基于这个事实：平面上 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}) （好玄学

代码在这里