向量乱杀

三维凸包

不多说，看题：

给出空间中 $n$ 个点，求凸包最小表面积

增量法

增量法可以解决很多问题，它每次把一个问题化为同类型的、规模更小的问题，可以表示为 $T(n) = T(n - 1) + g(n)$

考虑三维凸包，它一定是由一个个平面组成，和二维一样，我们先确定一个平面，然后不断地往里加点，每次加一个点，更新一下凸包，直到所有点都加进来了，整个的凸包也就求完了，这就是增量法的思想

那么问题是，如何更新凸包才能使得加入一个点后，更新为一个新的多面体，是 $i+1$ 个点的凸包

如上图：每当新加一个点 $p_r$ 时，将这个点想成一个光源（太阳），向四周散发光线（如图二），照到原先的凸多面体 $CH$ 上，所有能被照到的平面是要删去的面，所有照不到的面是要留下来的

然后看所有边，每条边都在两个平面上（两平面的交线），当光线照到他所在平面时，代表该边被照到一次，然后我们找出所有被照到一次的边，说明他们是能照到和不能照到的分界线，所以我们新加一个该边和新加入的 $p_r$ 点所构成的一个平面（如图三），就是新凸多面体

还有一些细节：

存每个平面时都只存三角形平面，即存三个顶点，但若存在 $n$ 边形的平面，可以划分成 $n - 2$ 个三角形
如何判断一个点能照到的平面呢？可以判断这个点在平面上方还是下方（通过和法向量的点积判断，具体可以看这个），在上面说明能照到，在下面说明照不到，所以这里的平面是有方向的，因此我们存平面时一定要严格按照一个方向存三个点，这里统一规定逆时针存
如何判断每条边被照到了几次？我们加个 bool 二维数组， g[a][b] 为 $1$ 的话说明 $a$ 到 $b$ 的边被照到一次，所以当 g[a][b] 为 $1$ ， g[b][a] 为 $0$ 时说明 $ab$ 这条边只被照到了一次。（因为都是逆时针存点，所以这个面是 $ab$ 边时，邻面就是 $ba$ 边）
如何解决多点共面的情况？给每个点都加一个微小扰动，就是让他的坐标发生一个很细微很细微的变化，使得不存在四点共面的情况（存在概率极小），然后任意三个点就可以构成一个唯一平面了

代码

板子

#include <bits/stdc++.h>
#define STC static
#define LL long long
#define DB double
#define DRG default_random_engine
#define URD uniform_real_distribution
using namespace std;
const int N = 2000 + 5;
const DB PI = acos(-1), eps = 1e-12;
DRG e{20051221};
URD<DB> u{-0.5, 0.5};
struct Point
{
    DB x, y, z;
    void shake()
    {
        x += u(e) * eps, y += u(e) * eps, z += u(e) * eps;
    } 
    Point operator - (const Point &t) const
    {
        return {x - t.x, y - t.y, z - t.z};
    }
    DB operator & (const Point &t) const
    {
        return x * t.x + y * t.y + z * t.z;
    }
    Point operator * (const Point &t) const
    {
        return {y * t.z - t.y * z, z * t.x - x * t.z, x * t.y - y * t.x};
    }
    DB len()
    {
        return sqrt(x * x + y * y + z * z);
    }
} ;
struct Plane
{
    Point v[3];
    int id[3];
    Point norm() //法向量
    {
        return (v[1] - v[0]) * (v[2] - v[0]);
    }
    DB area()
    {
        return norm().len() / 2;
    }
    bool above(Point x)
    {
        return ((x - v[0]) & norm()) >= 0;
    }
} ;
void convex_3d(Point x[], int len, Plane p[], int &lp)
{
    STC bool g[N][N];
    STC Plane np[N];
    p[lp++] = {x[0], x[1], x[2], 0, 1, 2};
    p[lp++] = {x[2], x[1], x[0], 2, 1, 0};
    for (int i = 3; i < len; ++i)
    {
        int cnt = 0;
        for (int j = 0; j < lp; ++j)
        {
            bool t = p[j].above(x[i]);
            if (!t)
                np[cnt++] = p[j];
            for (int k = 0; k < 3; ++k)
                g[p[j].id[k]][p[j].id[(k + 1) % 3]] = t;
        }
        for (int j = 0; j < lp; ++j)
            for (int k = 0; k < 3; ++k)
            {
                int a = p[j].id[k], b = p[j].id[(k + 1) % 3];
                if (g[a][b] && !g[b][a])
                    np[cnt++] = {x[a], x[b], x[i], a, b, i};
            }
        lp = cnt;
        for (int j = 0; j < lp; ++j)
            p[j] = np[j];
    }
}
int main()
{
    int n, m;
    scanf("%d", &n);
    STC Point q[N];
    STC Plane p[N];
    for (int i = 0; i < n; ++i)
        scanf("%lf %lf %lf", &q[i].x, &q[i].y, &q[i].z), q[i].shake();
    convex_3d(q, n, p, m);
    DB ans = 0;
    for (int i = 0; i < m; ++i)
        ans += p[i].area();
    printf("%.3lf\n", ans);
    return 0;
}