自动搬运

查看原文

来自洛谷，原作者为

	NOI_Winner AFO on 2025.7.18

搬运于2025-08-24 21:35:58，当前版本为作者最后更新于2025-01-21 12:51:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：求 $n$ 个点的三维凸包的表面积。（$n \le 100$）

先对所有点的位置进行微小扰动，以防止出现四点共面的情况。

我们可以枚举这些点能够组成的所有三角形，如果剩余所有点全部在该三角形所在平面的同一侧，那这个三角形就在这个三维凸包上，直接让答案加上它的面积即可。

怎样求若干个点是否在三角形所在平面的同一侧呢？设三角形为 $\triangle ABC$，求出 $\overrightarrow{AB} \times \overrightarrow{AC}$（叉乘），也就是该平面的法向量，记为向量 $\boldsymbol{v}$。枚举剩余的点，设当前点为 $D$，求出 $\overrightarrow{AD} \cdot \boldsymbol{v}$（点乘）。如果存在两个点求出来的值一正一负，就说明这两个点在平面的两侧。三角形的面积即为 $\frac{|\boldsymbol{v}|}{2}$。

算法的时间复杂度为 $O(n^4)$。

代码示例：

#include <iostream>
#include <random>
#include <ctime>
#include <limits> 
#include <cmath>

using namespace std;

constexpr int maxn = 100;
constexpr double eps = 1e-10;
mt19937 rd(time(nullptr));

struct point
{
	double x, y, z;
} a[maxn + 5];

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

inline double get_delta()    // 微小扰动的值
{ return (1. * rd() / numeric_limits<unsigned>::max() - 0.5) * eps; }

inline vec operator-(const point& a, const point& b)      // 求出向量
{ return {b.x - a.x, b.y - a.y, b.z - a.z}; }

inline double operator*(const vec& a, const vec& b)      // 点乘
{ return a.x * b.x + a.y * b.y + a.z * b.z; }

inline vec operator^(const vec& a, const vec& b)     // 叉乘
{ return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x}; }

inline double get_mod(const vec& a)     // 求向量的模长
{ return sqrt(a.x * a.x + a.y * a.y + a.z * a.z); }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	(cout << fixed).precision(6);
	
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y >> a[i].z;
	for (int i = 1; i <= n; i++)    // 微小扰动
	{
		a[i].x += get_delta();
		a[i].y += get_delta();
		a[i].z += get_delta();
	}
	
	double ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			for (int k = j + 1; k <= n; k++)
			{
				vec cur = (a[j] - a[i]) ^ (a[k] - a[i]);
				bool flag1 = false, flag2 = false;
				for (int l = 1; l <= n; l++)
					if (i != l && j != l && k != l)
					{
						if (cur * (a[l] - a[i]) > 0)
							flag1 = true;
						else
							flag2 = true;
					}
				if (!flag1 || !flag2)
					ans += get_mod(cur) / 2;   // 加上面积
			}
	cout << ans << endl;
	
	return 0;
}