题解 P2287 【[HNOI2004]最佳包裹】
SuperJvRuo
2018-06-13 19:04:25
显然这道题是要求三维凸包的表面积，常用的方法是卷包裹法和增量法，~~我都不会~~。此题数据范围较小，可以直接暴力$O(n^4)$水过。精通计算几何的大佬可以介绍一下卷包裹法和增量法。
$O(n^3)$枚举点集中的三个点，再用$O(n)$扫一遍其他点，如果其他点都在这三个点形成的面的同一侧，那么这个面就在凸包上。
那么如何判断点$P$在面$ABC$的哪一侧呢？只要求出面$ABC$的一个法向量（叉积即可），再用点积算一下$\vec{AP}$与法向量的夹角余弦值即可。余弦为正的点在一侧，余弦为负的在另一侧。
但是只这么做会WA的很惨，因为会有四点共面的情况存在。你需要让点抖一抖来避免共面的出现。
然后，见证暴力的奇迹吧：
```
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define EPS 1e-10
//设EPS为1e-9时爆精度只得了75分，可能是脸黑
struct Point
{
double x,y,z;
}point[105];
int n;
typedef Point Vector;
double rand01()
{
return rand()/(double)RAND_MAX;
}
double randeps()
{
return (rand01()-0.5)*EPS;
}
Vector add_noise(Vector p)
{
return (Vector){p.x+randeps(),p.y+randeps(),p.z+randeps()};
}//生成一个一定EPS内的抖动
Vector operator - (Vector a,Vector b)
{
return (Vector){a.x-b.x,a.y-b.y,a.z-b.z};
}//减法
double mod(Vector a)
{
return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);
}//模长
double Dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y+a.z*b.z;
}//点积，也就是数量积
Vector Cross(Vector a,Vector b)
{
return (Vector){a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};
}//叉积，也就是向量积
double area(Vector a,Vector b)
{
return 0.5*mod(Cross(a,b));
}//面积，叉积模长的一半
bool check(int p1,int p2,int p3)
{
double head=0,now;
Vector normal=Cross(point[p1]-point[p2],point[p2]-point[p3]);//将叉积作为法向量
for(int i=0;i<n;++i)
{
if(i!=p1&&i!=p2&&i!=p3)
{
if((now=Dot(point[i]-point[p1],normal))*head<0)
{//点积与余弦值一定同号
return false;
}
else
{
head=now;
}
}
}
return true;
}
int main()
{
scanf("%d",&n);
double res=0;
for(int i=0;i<n;++i)
{
scanf("%lf %lf %lf",&point[i].x,&point[i].y,&point[i].z);
point[i]=add_noise(point[i]);//让点抖动一下
}
for(int i=0;i<n;++i)
{
for(int j=i+1;j<n;++j)
{
for(int k=j+1;k<n;++k)
{
if(check(i,j,k))
{//所有的点都在一侧
res+=area(point[i]-point[j],point[j]-point[k]);//就加上这个面的面积
}
}
}
}
printf("%.6lf",res);
return 0;
}
```