描述

求出覆蓋n個點的最小圓

增量法

假設圓O是前i-1個點得最小覆蓋圓丧诺，加入第i個點脯颜，如果在圓內或邊上則什么也不做悠汽。否則,新得到的最小覆蓋圓肯定經(jīng)過第i個點。 然后以第i個點為基礎（半徑為0）缸棵，重復以上過程依次加入第j個點舟茶，若第j個點在圓外，則最小覆蓋圓必經(jīng)過第j個點堵第。 重復以上步驟（因為最多需要三個點來確定這個最小覆蓋圓吧凉，所以重復三次）。遍歷完所有點之后踏志，所得到的圓就是覆蓋所有點得最小圓阀捅。

證明

最小圓必定是可以通過不斷放大半徑，直到所有以任意點為圓心针余，半徑為半徑的圓存在交點饲鄙，此時的半徑就是最小圓。所以上述定理可以通過這個思想得到圆雁。這個做法復雜度是O(n)的忍级，當加入圓的順序隨機時，因為三點定一圓伪朽，所以不在圓內概率是3/i,求出期望可得是O(n)轴咱。

TypeScript代碼實現(xiàn)

interface Position {
    x: number;
    y: number;
}

interface Circle {
    center: Position;
    radius: number;
}

/**
 * @desc 求兩點間距離
 * @param a: Position
 * @param b: Position
 */
function len(a: Position, b: Position) {
    return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));
}

/**
 * @desc 求三角形外接圓
 * @param a
 * @param b
 * @param c
 */
function circleOfTriangle(a: Position, b: Position, c: Position): Circle {

    const a1 = 2 * (b.x - a.x),
          b1 = 2 * (b.y - a.y),
          c1 = b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y,
          a2 = 2 * (c.x - b.x),
          b2 = 2 * (c.y - b.y),
          c2 = c.x * c.x + c.y * c.y - b.x * b.x - b.y * b.y;

    const center = {
        x: (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1),
        y: (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1)
    };

    const circle = {
        center: center,
        radius: len(a, center)
    };

    return circle;
}

/**
 * @desc 最小覆蓋圓
 */
function minCircle(pArr: Array<Position>) {
    let tempCircle = {
        center: pArr[0],
        radius: 0
    };

    for (let i = 0; i < pArr.length; i++) {
        if (len(pArr[i], tempCircle.center) > tempCircle.radius) {
            tempCircle.center = pArr[i];
            tempCircle.radius = 0;

            for (let j = 0; j < i; j++) {
                if (len(pArr[j], tempCircle.center) > tempCircle.radius) {
                    tempCircle.center = {
                        x: (pArr[i].x + pArr[j].x) / 2,
                        y: (pArr[i].y + pArr[j].y) / 2
                    };
                    tempCircle.radius = len(pArr[i], pArr[j]) / 2;

                    for (let k = 0; k < j; k++) {
                        if (len(pArr[k], tempCircle.center) > tempCircle.radius) {
                            tempCircle = circleOfTriangle(pArr[i], pArr[j], pArr[k]);
                        }
                    }
                }
            }
        }
    }

    return tempCircle;
}