【题解】hull 三维凸包 计算几何 BZOJ – 1964

题目链接

搜题解第一篇文章居然是 achen 的 https://www.cnblogs.com/Achenchen/p/9502235.html

讲的好哇，做法很简洁：

二维平面四个点求凸包面积->任选三个点面积之和/2
三维空间五个点求凸包体积->任选四个点体积之和/2
二维平面三个点面积->二个二维向量行列式值的绝对值/2
三维空间四个点体积->三个三维向量行列式值的绝对值/6

究其原因是每个坐标会被所有的三角/四棱锥剖分覆盖两次

#include <bits/stdc++.h>

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

double X[10], Y[10], Z[10], ans;

double cal(int a, int b, int c, int d)
{
    double x1 = X[b] - X[a], x2 = X[c] - X[a], x3 = X[d] - X[a];
    double y1 = Y[b] - Y[a], y2 = Y[c] - Y[a], y3 = Y[d] - Y[a];
    double z1 = Z[b] - Z[a], z2 = Z[c] - Z[a], z3 = Z[d] - Z[a];
    double res = x1 * y2 * z3 - x3 * y2 * z1 + y1 * z2 * x3 - x1 * z2 * y3
        + z1 * x2 * y3 - y1 * x2 * z3;
    return fabs(res) / 6;
}

int main(int argc, char const* argv[])
{
    for (int i = 1; i <= 5; i += 1) IN(X[i]), IN(Y[i]), IN(Z[i]);
    for (int i = 1; i <= 5; i += 1)
        for (int j = i + 1; j <= 5; j += 1)
            for (int k = j + 1; k <= 5; k += 1)
                for (int l = k + 1; l <= 5; l += 1)
                    ans += cal(i, j, k, l);
    printf("%.2f\n", ans * 0.5);
    return 0;
}