有随机化的调整思想也可以用在几何问题中。比如Ural1578的MammothHu
t：给出平面上的
个点，找一条
1段的折线将点连接起来，并且相邻两段折线的夹角是锐角。我们可以先任意生成一条折线，并且按一定规则进行调整，直到满足要求。
4
fIOI2008冬令营论文顾研
2随机增量算法
21增量算法
增量法（I
creme
talAlgorithm）的思想与第一数学归纳法类似，它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。写成递归式是：
T
T
1g
增量法形式简洁，可以应用于许多几何题目中。
22随机增量算法的一个例子
增量法的优势在于它是线性递增的，代码实现通常比较简单，但是时间复杂度相对比较高1，尤其在ACMICPC竞赛中，一个极限数据很容易成为算法的瓶颈，导致TLE。因此，增量算法往往结合舍伍德算法的思想（随机），成为“随机增量算法”，在一大类问题中大大改进了平均情况下的时间复杂度。在增量算法中加入舍伍德算法（随机化），我们要做两件事：（1）给出一个高效的随机洗牌算法。这个问题不复杂，以下代码就可以以线性的时间复杂度得到一个1
的随机排列。（记录在数组O中。）AlgorithmRa
dom_shufflefori2to
交换Oi，Ora
domi（其中ra
dom
返回一个1
的随机数。）（2）计算随机化后
种等概率的顺序的时间复杂度的数学期望的平均值。这个问题将在引例中讨论。
引例：最小外接圆（经典问题）2
题目描述：已知平面上
个点的坐标，求能够覆盖所有的点的最小圆。
12
构造极限数据很容易。可在zju1450提交。5
fIOI2008冬令营论文顾研
分析：本节主要讨论随机增量算法，仅在张角法前提下分析一些随机增量算法的性质。
221张角法
首先，易知至少有两个点在圆上（除非总共只有一个点）。我们首先枚举这两个点（设为AB）。初中的平面几何知识告诉我们对于同一段弧，圆周角小于圆内角（如），设AB上方最小的张图1
角为，下方最小的张角为，则当时，△ABC或△ABD的外接圆可以覆盖所有的点。特别地，当时ABCD四点共圆。可以看到，该算法的时间复杂度为O
3，并且是一个确定性算法。

222改进算法我们用Pp1p
表示题目中的点。考虑使用增量算法，令Pp1pi，Dii则代表相对于Pi的最小外接圆。定理：设2i
，有：（i）（ii）若piDi1，则DiDi1；（这个非常显然。）若piDi1，则pi必然落在Di的边界上r