BZOJ [1336/1337/2823] [Balkan2002]Alien 最小圆覆盖/[AHOI2012] 信号塔

发布于 2017-07-10  265 次阅读


题目链接:

http://www.lydsy.com/JudgeOnline/problem.php?id=1336

http://www.lydsy.com/JudgeOnline/problem.php?id=1337

http://www.lydsy.com/JudgeOnline/problem.php?id=2823

题意:给出平面上 N 个点,N<=10^5,请求出一个半径最小的圆覆盖住所有的点,并求出该点的坐标。


一口气的三倍经验...

随机增量法是一个可以在 期望 \(O(n)\) 时间内求出最小圆覆盖的算法,首先它的算法流程是这样的

枚举第一个点 i,若不在目前圆内,设它为圆心

枚举第二个点 j,若不在当前圆内,设当前圆为以 i,j 为直径的圆

枚举第三个点 k,若不在当前圆内,设当前圆为 i,j,k 的外接圆

正确性


显然最优解一定是两个点为直径的圆或者一个三角形的外接圆,否则肯定能缩的更小。那么这么枚举的正确性是比较显然的了

时间复杂度


这是一个重点,这么做看似是\(O(n^3)\) 的,不过对于 随机顺序 的点,是可以 期望 \(O(n)\) 的。下面考虑证明:

显然,最后一层循环枚举从 1~j,只要进入循环就一定要跑完,所以是\(O(j)\) 的

考虑倒数第二层循环,什么情况下会进入第三层循环呢?仅当 j 不在前 j-1 个点形成的圆中,考虑 j 个点形成的圆是由三个点确定的,那么第 j 个 (最后一个点) 若是三个点之一,则需要扩大圆,否则不需要进入第三层循环,这个概率是\(\frac{3}{j}\) 的,所以第二层的复杂度是\(O(i)\) 的

同理,第一层的复杂度就是\(O(n)\) 的了

当然,这是基于随机数据的期望复杂度,所以我们一般需要手动打乱排列

实现


代码是相近的,在此以 2823 为例

另外.... 发现很多神犇在 get_O 时特判了几个等于 0 的情况... 并不能理解用处,求路过大爷指教

 

 


一个非常弱的准退役OIER