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)\)。
感觉其实并不算数学题？只是用了基础的几何知识而已。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 分享、互助 让互联网精神温暖你我 谢谢分享，辛苦了 很好很强大我过来先占个楼 待编辑 感谢分享 分享、互助 让互联网精神温暖你我 不错，里面软件多更新就更好了 yyds。多谢分享 这个好，看起来很实用 鼓励转贴优秀软件安全工具和文档！ 这个有用。 前排留名，哈哈哈 不错，里面软件多更新就更好了 这个有用。 收藏一下 不知道什么时候能用到 感谢分享，下载保存了，貌似很强大 这个有用。 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 谢谢分享，试用一下
页:
[1]
2