基于c++ 最小包围球WeIzI算法

最小包围球（Minimum Enclosing Ball）是一种用于包含给定点集的最小球体的算法。WeIzI算法是一种基于递归的最小包围球算法，它的时间复杂度为 O(n)。

以下是基于C++的WeIzI算法实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>

using namespace std;

const double eps = 1e-12;

struct Point {
    double x, y, z;
};

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

Point get_circumcenter(const Point &a, const Point &b, const Point &c) {
    double x1 = a.x, y1 = a.y, z1 = a.z;
    double x2 = b.x, y2 = b.y, z2 = b.z;
    double x3 = c.x, y3 = c.y, z3 = c.z;
    double A = x2 - x1, B = y2 - y1, C = z2 - z1;
    double D = x3 - x1, E = y3 - y1, F = z3 - z1;
    double G = A * (x1 + x2) + B * (y1 + y2) + C * (z1 + z2);
    double H = D * (x1 + x3) + E * (y1 + y3) + F * (z1 + z3);
    double I = 2 * (A * (y3 - y2) - B * (x3 - x2));
    double J = 2 * (D * (y2 - y1) - E * (x2 - x1));
    double K = 2 * (B * F - C * E);
    double x = (H * K - G * J) / (I * K - J * J);
    double y = (G - I * x) / J;
    double z = -(A * x + B * y + G) / C;
    return {x, y, z};
}

double get_radius(const Point &a, const Point &b, const Point &c) {
    Point o = get_circumcenter(a, b, c);
    return dis(o, a);
}

void WeiZi(const vector<Point> &p, int n, Point &c, double &r) {
    if (n == 0) {
        c = {0, 0, 0};
        r = -1;
        return;
    }
    if (n == 1) {
        c = p[0];
        r = 0;
        return;
    }
    if (n == 2) {
        c = {(p[0].x + p[1].x) / 2, (p[0].y + p[1].y) / 2, (p[0].z + p[1].z) / 2};
        r = dis(c, p[0]);
        return;
    }
    random_device rd;
    mt19937 gen(rd());
    shuffle(p.begin(), p.end(), gen);
    c = {(p[0].x + p[1].x + p[2].x) / 3, (p[0].y + p[1].y + p[2].y) / 3, (p[0].z + p[1].z + p[2].z) / 3};
    r = dis(c, p[0]);
    for (int i = 1; i < n; i++) {
        if (dis(c, p[i]) - r > eps) {
            vector<Point> q;
            for (int j = 0; j < i; j++) {
                if (dis(c, p[j]) - r > eps) {
                    q.push_back(p[j]);
                }
            }
            WeiZi(q, q.size(), c, r);
            r = dis(c, p[i]);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y >> p[i].z;
    }
    Point c;
    double r;
    WeiZi(p, n, c, r);
    cout << "Center: (" << c.x << ", " << c.y << ", " << c.z << ")" << endl;
    cout << "Radius: " << r << endl;
    return 0;
}

其中，`Point` 表示三维空间中的一个点，`dis` 函数计算两点之间的距离，`get_circumcenter` 函数计算三角形外心坐标，`get_radius` 函数计算三角形外接圆半径，`WeiZi` 函数是核心算法实现，它通过递归不断缩小包围球的半径和中心坐标。主函数中读入点集，调用 `WeiZi` 函数计算最小包围球的圆心和半径。