c++求球点云直径

求球点云的直径可以使用旋转卡壳算法。步骤如下：

1. 首先找到点云中的最左边和最右边的点，将它们连线得到一条直线。

2. 找到这条直线上距离最远的两个点，将它们连线得到的线段就是直径的一部分。

3. 对于每一个点，计算它和直线的距离。如果该点在直线的左侧，则距离为正数，否则为负数。

4. 找到距离最大的点，假设它在直线的左侧，那么它一定在球的左半部分。然后以该点为起点，重复步骤1-3，找到最远的点，这条线段就是直径的另一部分。

5. 直径的长度就是两部分线段长度之和。

下面是 C++ 代码实现：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

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

double distance(Point p1, Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    double dz = p1.z - p2.z;
    return sqrt(dx * dx + dy * dy + dz * dz);
}

double cross(Point p0, Point p1, Point p2) {
    double x1 = p1.x - p0.x;
    double y1 = p1.y - p0.y;
    double z1 = p1.z - p0.z;
    double x2 = p2.x - p0.x;
    double y2 = p2.y - p0.y;
    double z2 = p2.z - p0.z;
    return x1 * y2 * z2 + y1 * z2 * x2 + z1 * x2 * y2 - z1 * y2 * x2 - y1 * x2 * z2 - x1 * z2 * y2;
}

double diameter(vector<Point>& points) {
    int n = points.size();
    if (n <= 1) return 0;
    if (n == 2) return distance(points[0], points[1]);

    int p1 = 0, p2 = 0;
    for (int i = 1; i < n; i++) {
        if (points[i].x < points[p1].x) p1 = i;
        if (points[i].x > points[p2].x) p2 = i;
    }
    double max_dist = distance(points[p1], points[p2]);

    vector<int> left, right;
    for (int i = 0; i < n; i++) {
        if (cross(points[p1], points[p2], points[i]) > 0) left.push_back(i);
        else if (cross(points[p1], points[p2], points[i]) < 0) right.push_back(i);
    }

    int q1 = 0, q2 = 0;
    for (int i = 0; i < left.size(); i++) {
        while (q1 + 1 < left.size() && cross(points[left[i]], points[left[q1]], points[left[q1 + 1]]) < 0) q1++;
        while (q2 + 1 < right.size() && cross(points[right[i]], points[right[q2]], points[right[q2 + 1]]) > 0) q2++;
        max_dist = max(max_dist, distance(points[left[i]], points[right[q2]]));
        max_dist = max(max_dist, distance(points[right[i]], points[left[q1]]));
    }

    return max_dist;
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y >> points[i].z;
    }
    double d = diameter(points);
    cout << d << endl;
    return 0;
}

其中，`Point` 结构体表示三维空间中的点，`distance` 函数计算两点之间的距离，`cross` 函数计算三个点构成的向量的叉积，`diameter` 函数实现旋转卡壳算法。最后，读入点云数据，调用 `diameter` 函数即可求出直径的长度。