最小外包圆算法源码实现。

最小外包圆算法（Minimum Enclosing Circle）是一种寻找平面点集最小外接圆的算法。以下是一份C++实现的源码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const double eps = 1e-8;
const double PI = acos(-1.0);

struct Point {
    double x, y;
}p[N], q[N], O;

int n;

double dis(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double cross(Point a, Point b, Point c) {
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

Point getO(Point A, Point B, Point C) {
    double a1 = B.x-A.x, b1 = B.y-A.y, c1 = (a1*a1+b1*b1)/2;
    double a2 = C.x-A.x, b2 = C.y-A.y, c2 = (a2*a2+b2*b2)/2;
    double d = a1*b2-a2*b1;
    O.x = A.x+(c1*b2-c2*b1)/d;
    O.y = A.y+(a1*c2-a2*c1)/d;
    return O;
}

void MEC() {
    random_shuffle(p+1, p+1+n);
    O = p[1];
    double R = 0;
    for(int i = 2; i <= n; i++) {
        if(dis(O, p[i]) < R+eps) continue;
        O = p[i]; R = 0;
        for(int j = 1; j < i; j++) {
            if(dis(O, p[j]) < R+eps) continue;
            O.x = (p[i].x + p[j].x) / 2.0;
            O.y = (p[i].y + p[j].y) / 2.0;
            R = dis(O, p[i]);
            for(int k = 1; k < j; k++) {
                if(dis(O, p[k]) < R+eps) continue;
                O = getO(p[i], p[j], p[k]);
                R = dis(O, p[i]);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    MEC();
    printf("%.2f %.2f %.2f\n", O.x, O.y, dis(O, p[1]));
    return 0;
}

其中，dis函数计算两点之间的距离，cross函数计算向量OA和向量OB的叉积，getO函数计算以A、B、C三点为直径的圆的圆心坐标。最小外包圆算法的核心部分在MEC函数中，利用随机增量法和三点定圆法来找到最小圆。