C++ WeIzI最小包围球算法

以下是C++实现WeIzI最小包围球算法的示例代码：

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-12;
const double INF = 1e100;
const double PI = acos(-1.0);

struct Point {
    double x, y, z;
    Point() {}
    Point(double x, double y, double z) : x(x), y(y), z(z) {}
};

struct Sphere {
    Point o;
    double r;
    Sphere() {}
    Sphere(Point o, double r) : o(o), r(r) {}
};

double sqr(double x) { return x * x; }

double dist(Point a, Point b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y) + sqr(a.z - b.z));
}

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

double dot(Point a, Point b) { return a.x * b.x + a.y * b.y + a.z * b.z; }

Point operator+(Point a, Point b) { return Point(a.x + b.x, a.y + b.y, a.z + b.z); }

Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y, a.z - b.z); }

Point operator*(Point a, double k) { return Point(a.x * k, a.y * k, a.z * k); }

Point operator/(Point a, double k) { return Point(a.x / k, a.y / k, a.z / k); }

Sphere minSphere(Point *ps, int n, vector<Point> &ch) {
    random_shuffle(ps, ps + n);
    Sphere s(Point(0, 0, 0), -INF);
    for (int i = 0; i < n; i++) {
        if (dist(ps[i], s.o) > s.r + eps) {
            ch.clear();
            ch.push_back(ps[i]);
            s = Sphere(ps[i], 0);
            for (int j = 0; j < i; j++) {
                if (dist(ps[j], s.o) > s.r + eps) {
                    ch.clear();
                    ch.push_back(ps[i]);
                    ch.push_back(ps[j]);
                    s = Sphere((ps[i] + ps[j]) / 2, dist(ps[i], ps[j]) / 2);
                    for (int k = 0; k < j; k++) {
                        if (dist(ps[k], s.o) > s.r + eps) {
                            ch.clear();
                            ch.push_back(ps[i]);
                            ch.push_back(ps[j]);
                            ch.push_back(ps[k]);
                            Point u = (ps[j] - ps[i]) / dist(ps[i], ps[j]);
                            Point v = cross(ps[j] - ps[i], ps[k] - ps[i]) / dist(ps[i], ps[j]);
                            double theta = atan2(dot(ps[k] - ps[i], v), dot(ps[k] - ps[i], u));
                            Point c = ps[i] + u * s.r * cos(theta) + v * s.r * sin(theta);
                            s = Sphere(c, dist(c, ps[k]));
                        }
                    }
                }
            }
        }
    }
    return s;
}

int main() {
    int n;
    cin >> n;
    Point ps[n];
    for (int i = 0; i < n; i++) {
        cin >> ps[i].x >> ps[i].y >> ps[i].z;
    }
    vector<Point> ch;
    Sphere s = minSphere(ps, n, ch);
    cout << fixed << setprecision(8) << s.r << endl;
    return 0;
}

以上代码使用了随机化的方法选取最开始的一些点，然后使用递归的方式求解最小包围球。其中，dist函数用于计算两点之间的距离，cross函数用于计算两向量的叉积，dot函数用于计算两向量的点积。minSphere函数就是WeIzI最小包围球算法的具体实现。输入的数据格式是n个三维点的坐标，输出的是最小包围球的半径。