• 问题描述：平面上$n$个点, 要求找到一个半径最小的圆, 能覆盖所有的点.

算法思想: 随机增量法 (理论实践复杂度O(n) ? 但是最坏貌似还是$n^3$) 每次进入下一曾 for的概率都小于$\frac{3}{n}$. 因此每次随机化点可以尽可能地避免最坏情况的发生.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

int n;
Points ps(n);
random_shuffle(ps.begin(), ps.end()); // 随机化
Circle res(Point(0, 0), 0);
for(int i = 0; i < n; i ++) {
    // 圆是否包含点 i
    if(CCP(res, ps[i]) == out) {
        res = Circle(ps[i], 0);
        for(int j = 0; j < i; j ++) {
            if(CCP(res, ps[j]) == out) {
                // 两点确定一个圆
                res = Circle((ps[i] + ps[j]) / 2, dis(ps[i], ps[j]) / 2);
                for(int k = 0; k < j; k ++) {
                    if(CCP(res, ps[k]) == out) {
                        // 三点确定一个圆
                        res = circumcircle(ps[i], ps[j], ps[k]);
                    }
                }
            }
        }
    }
}