1209: [HNOI2004]最佳包裹
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 160 Solved: 58
[Submit][Status][Discuss]
Description
H
公司生产了一种金属制品，是由一些笔直的金属条支撑起来的，金属条和别的金属条在交点上被焊接在了一起。现在由于美观需要，在这个产品用一层特殊的材料包
裹起来。公司为了节约成本，希望消耗的材料最少（不计裁剪时的边角料的损失）。你的程序需要根据给定的输入，给出符合题意的输出：
输入包括该产品的顶点的个数，以及所有顶点的坐标； 你需要根据输入的计算出包裹这个产品所需要的材料的最小面积。
结果要求精确到小数点后第六位。（四舍五入）
Input
第1行是一个整数n(4 <= n <= 100)，表示顶点的个数；第2行到第n+1行，每行是3个实数xi,yi,zi，表示第i个顶点的坐标。每个顶点的位置各不相同。
Output
输出只有一个实数，表示包裹一个该产品所需的材料面积的最小值。
Sample Input
4
0 0 0
1 0 0
0 1 0
0 0 1 说明：该输入示例*有4个点，可参见后面的图示。
0 0 0
1 0 0
0 1 0
0 0 1 说明：该输入示例*有4个点，可参见后面的图示。
Sample Output
2.366025
HINT
这道题算是三维凸包的模板题吧，话说网上的三维凸包的教程中判三点共线，四点共面的方法确实有些复杂，经过idy博客的启发，其实在做凸包前对每个点加一遍噪音就行了。如果一个点可以看见当前一个面，那么这个面就会被删除，其表现就是有向体积为负数，删除一个面的同时，删除这个面的三条边（也是有向的）最有扫一遍观察哪些边的反向边不存在，然后将他们的反向边与当前加的点一同构成新的凸包。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<assert.h>
#include<vector>
using namespace std;
#define MAXN 120
#define eps 1e-11
typedef double real;
inline int sgn(real x)
{
if (abs(x)<eps)return ;
return x<?-:;
}
struct point
{
real x,y,z;
point(real x,real y,real z):x(x),y(y),z(z){}
point(){}
int read()
{
return scanf("%lf %lf %lf\n",&x,&y,&z);
}
void noise()
{
x+=(real)(rand()%-)/*eps;
y+=(real)(rand()%-)/*eps;
z+=(real)(rand()%-)/*eps;
}
real len()
{
return sqrt(x*x+y*y+z*z);
}
};
typedef point vect;
struct line
{
point ps;
real x,y,z;
line(){}
line(point p1,point p2)
{
ps=p1;
x=p2.x-p1.x;
y=p2.y-p1.y;
z=p2.z-p1.z;
}
line(point ps,real x,real y,real z):ps(ps),x(x),y(y),z(z){}
};
vect xmul(line l1,line l2)
{
return vect(l1.y*l2.z-l1.z*l2.y,l1.z*l2.x-l1.x*l2.z,l1.x*l2.y-l1.y*l2.x);
}
real volume(line l1,line l2,line l3)
{
return + l1.x*l2.y*l3.z - l1.x*l2.z*l3.y
- l1.y*l2.x*l3.z + l1.y*l2.z*l3.x
+ l1.z*l2.x*l3.y - l1.z*l2.y*l3.x;
}
//+1 2 3
//-1 3 2
//-2 1 3
//+2 3 1
//+3 1 2
//-3 2 1
struct surface
{
point ps;
real x1,y1,z1;
real x2,y2,z2;
surface(){}
surface(point p1,point p2,point p3)
{
ps=p1;
x1=p2.x-p1.x,y1=p2.y-p1.y,z1=p2.z-p1.z;
x2=p3.x-p1.x,y2=p3.y-p1.y,z2=p3.z-p1.z;
}
real volume(point pt)
{
return ::volume(line(ps,pt),line(ps,x1,y1,z1),line(ps,x2,y2,z2));
}
vect nvect()
{
return xmul(line(ps,x1,y1,z1),line(ps,x2,y2,z2));
}
void reverse()
{
swap(x1,x2);
swap(y1,y2);
swap(z1,z2);
}
};
point pl[MAXN];
struct face
{
int pt[];
face(int x,int y,int z)
{
pt[]=x;pt[]=y;pt[]=z;
}
surface ToSurface()
{
return surface(pl[pt[]],pl[pt[]],pl[pt[]]);
}
void print()
{
printf("Face:%d %d %d\n",pt[],pt[],pt[]);
}
};
vector<face> cc;
vector<pair<int,int> > chs;
bool status[MAXN][MAXN];
int main()
{
freopen("input.txt","r",stdin);
int n;
scanf("%d",&n);
for (int i=;i<n;i++)
pl[i].read();
for (int i=;i<n;i++)
pl[i].noise();
/* for (int i=0;i<n;i++)
swap(pl[rand()%n],pl[rand()%n]);*/
cc.push_back(face(,,));
cc.push_back(face(,,));
for (int i=;i<;i++)
status[i][(i+)%]=true;
for (int i=;i<;i++)
status[i%][i-]=true;
for (int i=;i<n;i++)
{
//for (int j=0;j<cc.size();j++)cc[j].print(); printf("\n");
chs.clear();
for (int j=;j<cc.size();j++)
{
if (cc[j].ToSurface().volume(pl[i])<)
{
for (int k=;k<;k++)
{
status[cc[j].pt[k]][cc[j].pt[(k+)%]]=false;
chs.push_back(make_pair(cc[j].pt[k],cc[j].pt[(k+)%]));
}
swap(cc[j],cc[cc.size()-]);
cc.pop_back();
j--;
}
}
for (int j=;j<chs.size();j++)
{
if (!status[chs[j].first][chs[j].second] && status[chs[j].second][chs[j].first])continue;
chs[j]=chs[chs.size()-];
j--;
chs.pop_back();
}
for (int j=;j<chs.size();j++)
{
cc.push_back(face(i,chs[j].first,chs[j].second));
status[i][chs[j].first]=status[chs[j].first][chs[j].second]=status[chs[j].second][i]=true;
}
for (int j=;j<n;j++)
for (int k=;k<n;k++)
assert(!(status[j][k]^status[k][j]));
}
//for (int j=0;j<cc.size();j++)cc[j].print(); printf("\n");
real ans=;
for (int i=;i<cc.size();i++)
ans+=cc[i].ToSurface().nvect().len()/;
printf("%.6lf\n",abs(ans));
}