AC. 梦想

frank_c1

[BZOJ 1336] 最小圆覆盖

发布于2016年01月30日 | 暂无评论 | 1,268阅读 | 圆球相关,随机化

题目描述

给出N个点,画一个最小的包含所有点的圆。

输入格式

先给出点的个数N \; (2 \le N \le 100000),再给出坐标x_i,y_i \; (-10000.0 \le x_i,y_i \le 10000.0)

输出格式

输出圆的半径,及圆心的坐标。

题目解析

最小覆盖圆问题是计算几何中的经典问题,对于本题有一种神奇的算法——随机增量法。考虑暴力,可以枚举任意三点确定一个圆,求半径最小的,时间复杂度O(N ^ 3),这次介绍的随机增量法可以却可以做到期望时间复杂度O(N)

随机增量法具体过程如下:(1)将所有平面上的点随机排列;(2)先以点1,2确定直径,作出一个圆;(3)向后扫,将点逐个加入最小覆盖圆中,如果该点已在当前圆中或在圆上,则无需考虑,跳过;若不是,那么这个点一定是新的最小覆盖圆上的一个点,我们以这个点作为定点,用同样的方法来找第二个点、第三个点,确定三点后即可确定点1—i的最小覆盖圆;(4)重复步骤3,即可得到点1—n的最小覆盖圆。

这样一看,似乎依次确定三点的复杂度也是O(N ^ 3)?但这个算法中有一个很重要的因素:随机。运用概率的知识,我们可以分析它的期望时间复杂度。首先,我们确定了前i - 1个点的最小覆盖圆后,第i个点在圆外的概率是\frac{3}{i}(三点确定一圆),而根据确定点i重新求出1 - i的最小覆盖圆的复杂度为O(i),故根据期望可加性得T(N) = \sum\limits_{i = 1}^N {O(i){\rm{\cdot}}} \frac{3}{i} = O(N)

最后还有几个小细节:(1)已知不共线的三点怎样求出它们的外接圆?求任意两条两点间连线的中垂线,然后求两条中垂线的交点即可得圆心。(2)如果有三点共线怎么办?这题情况特殊,应用随机增量法时,不会出现共线的三点。考虑反证法,如果有三点k,j,i \; (k \lt j \lt i) 共线,则k不会是中间的那个点(否则不会进入循环),也不会是两侧的点(否则在之前就应该已经更新了最小覆盖圆),故不存在三点共线情况。