二分答案,并假设有一个点在圆周上,否则可以调整到更优。
枚举这个点,想象这个圆绕着这个点转一周的过程(也就是,扫描圆心对这个点的角度)。意在转的过程中,半径会实时发生变化。
对于每个其他的点,存在一个角度区间使得其在圆中。可以二分求出这个区间。
求出区间后,对角度扫描线即可。
直接做的时间复杂度是 O(n2lognlog1ϵ)O(n^2\log n\log \frac{1}{\epsilon})O(n2lognlogϵ1),可以通过随机打乱 + 只对改变答案的点二分的 trick 优化到 O(n2logn+nlog2nlog1ϵ)O(n^2\log n + n\log^2 n \log \frac{1}{\epsilon})O(n2logn+nlog2nlogϵ1)。
注册一个 oirush 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 oirush 通用账户