CF333E Summer Earnings

推歌：Between Worlds

很有意思的题。

注意到题目其实就是选三个点使得两两之间欧几里得距离最小值最大，很容易就有 \(O(n^3)\) 做法。

常规方法是注意到本题时限极大，而最小值最大又是可以从大到小枚举最小值的，因此把所有的点对按照距离排序从大到小扫，每次就是对 \((i,j)\) 求是否有 \(k\) 使得 \((i,k)\) 和 \((k,j)\) 的距离都比它大，可以很容易地用 Bitset 维护，\(O(\frac{n^3}{\omega})\) 即可通过。

但是有没有不靠 \(\omega\) 的方法呢？让我们使用一些中学学过的数学知识。

初中有一句话叫做“大角对大边”（其实就是正弦定理）而题目的问题又等价于求三角形中最短边的最大值，所以直接考虑枚举一个点 \(P\) 作为顶点。我们发现三角形的最小角一定是 \(\le \frac{\pi}{3}\) 的，如果以 \(P\) 为顶点的 \(\angle APB\ge \frac{\pi}{3}\)，那么此三角形的最短边一定在 \(PA\) 和 \(PB\) 中。

因此固定 \(A\) 后，我们要找的 \(B\) 就是使得 \(\angle APB\ge \frac{\pi}{3}\) 且 \(PB\) 最短的点，这是一个静态区间最小值！

然后我们就可以直接做了。枚举 \(P\)，将剩余的点以 \(P\) 为原点进行极角排序，ST 表预处理区间最小值，枚举 \(A\) 并快速求 \(B\)。由于每个点都会作为顶点出现所以不会有哪组最短边没扫到的情况。时间复杂度 \(O(n^2\log n)\)。

感觉其实并不算数学题？只是用了基础的几何知识而已。