最佳包裹问题

解题思路：

本题要求的其实就是 $n$ 个点三维凸包的面积，是一个三维凸包的模板题。将三维凸包求出来之后枚举每一个面求一下面积，累加在一起即可，由于存储的每个面都是一个三角形，因此可以直接用叉积求。

关于如何求三维凸包可以参考 三维计算机和基础和三维凸包的相关概念

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 210;
const double eps = 1e-10;

double rand_eps() //返回一个极小的随机值
{
    return ((double)rand() / RAND_MAX - 0.5) * eps;
}

struct Point
{
    double x, y, z;
    void shake() //将当前点进行随机扰动
    {
        x += rand_eps(), y += rand_eps(), z += rand_eps();
    }
    Point operator-(Point t) //重载向量减法
    {
        return {x - t.x, y - t.y, z - t.z};
    }
    double operator&(Point t) //重载点积
    {
        return x * t.x + y * t.y + z * t.z;
    }
    Point operator*(Point t) //重载叉积
    {
        return {y * t.z - t.y * z, z * t.x - x * t.z, x * t.y - y * t.x};
    }
    double len() //求模长
    {
        return sqrt(x * x + y * y + z * z);
    }
}q[N]; //存储所有点

struct Plane
{
    int v[3]; //三角形平面的三个顶点
    Point norm() //求平面法向量
    {
        return (q[v[1]] - q[v[0]]) * (q[v[2]] - q[v[0]]);
    }
    double area() //求平面的面积
    {
        return norm().len() / 2;
    }
    bool above(Point t) //判断 t 是否在平面的上方
    {
        return ((t - q[v[0]]) & norm()) >= 0;
    }
}plane[N], np[N]; //存储所有三角形平面，np 是备份数组

int n, m; //点数、面数
bool g[N][N]; //g[i][j] 表示 (i, j) 对应的面有没有被照到

void get_convex_3d()
{
    //最开始由头三个点构成凸包，有正、反两面
    plane[m++] = {0, 1, 2};
    plane[m++] = {2, 1, 0};
    for(int i = 3; i < n; i++)
    {
        int cnt = 0; //记录加入新点后所有的面
        for(int j = 0; j < m; j++)
        {
            bool t = plane[j].above(q[i]); //记录当前点是否在当前平面的上方
            if(!t) np[cnt++] = plane[j]; //如果当前点在当前平面下方，则当前平面应该保留
            for(int k = 0; k < 3; k++) g[plane[j].v[k]][plane[j].v[(k + 1) % 3]] = t; //记录当前面的每条边是否被照到
        }
        //在分界线上构造新面
        for(int j = 0; j < m; j++)
            for(int k = 0; k < 3; k++)
            {
                int a = plane[j].v[k], b = plane[j].v[(k + 1) % 3];
                if(g[a][b] && !g[b][a]) //如果当前边是分界线，构建新面
                    np[cnt++] = {a, b, i};
            }
        m = cnt;
        for(int j = 0; j < m; j++) plane[j] = np[j]; //将新凸包拷贝回原数组
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%lf%lf%lf", &q[i].x, &q[i].y, &q[i].z);
        q[i].shake(); //将当前点进行随机扰动
    }

    get_convex_3d(); //求三维凸包

    double res = 0; //记录三维凸包的面积
    for(int i = 0; i < m; i++) res += plane[i].area();
    printf("%.6lf\n", res);

    return 0;
}