记录编号	441204	评测结果	AAAAAAAAAAA
题目名称	[HNOI 2004] 金属包裹	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2017-08-24 17:43:55	内存使用	0.51 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;
typedef double db;
const db eps=1e-10;
const int N=110;
int sign(db x){
	if (x>eps) return 1;
	if (x<-eps) return -1;
	return 0;
}
struct vec{
	db x,y,z;
	vec(db X=0,db Y=0,db Z=0){x=X;y=Y;z=Z;}
	vec operator + (const vec a)const{return vec(x+a.x,y+a.y,z+a.z);}
	vec operator - (const vec a)const{return vec(x-a.x,y-a.y,z-a.z);}
	db operator * (const vec a)const{return x*a.x+y*a.y+z*a.z;}
	vec operator ^ (const vec a)const{return vec(y*a.z-z*a.y,z*a.x-x*a.z,x*a.y-y*a.x);}
	db length(){return sqrt(x*x+y*y+z*z);}
	bool operator == (const vec a)const{return !sign(x-a.x)&&!sign(y-a.y)&&!sign(z-a.z);}
	void print(){
		printf("(%.2lf,%.2lf,%.2lf) ",x,y,z);
	}
}p[N];
int n,m,sig[N];
bitset<N> ok[N][N];
vec q[N],dir,vx,vy;
db ans;
bool cmp(const vec &x,const vec &y){
	db x1=x*vx,x2=y*vx;
	return x1!=x2?x1<x2:x*vy<y*vy;
}
bool test(vec &x,vec &y,vec &z){
	return ((y-x)^(z-y))*dir>eps;
}
void calc(){//求q中点构成的面积,法向量为dir
	vx=q[2]-q[1];vy=dir^vx;
	sort(q+1,q+m+1,cmp);
	static vec Q[N*2];
	int head=1,tail=0;
	for (int i=1;i<=m;i++){
		for (;head<tail&&test(Q[tail-1],Q[tail],q[i]);tail--);
		Q[++tail]=q[i];
	}
	for (int i=m-1;i;i--){
		for (;head<tail&&test(Q[tail-1],Q[tail],q[i]);tail--);
		Q[++tail]=q[i];
	}
	for (int i=head+2;!(Q[i]==Q[head]);i++)
		ans+=0.5*((Q[i]-Q[1])^(Q[i-1]-Q[1])).length();
}
void test(int i,int j,int k){
	dir=(p[k]-p[i])^(p[j]-p[i]);
	if (dir.length()<eps) return;
	bool isneg=0,ispos=0;
	for (int l=1;l<=n;l++){
		sig[l]=sign((p[l]-p[i])*dir);
		if (sig[l]<0) isneg=1;
		if (sig[l]>0) ispos=1;
		if (isneg&&ispos) return;
	}
	static int que[N];
	m=0;
	for (int l=1;l<=n;l++)
		if (!sig[l]) q[++m]=p[l],que[m]=l;
	for (int a=1;a<=m;a++)
	for (int b=a+1;b<=m;b++)
	for (int c=b+1;c<=m;c++)
		ok[que[a]][que[b]][que[c]]=1;
	calc();
	if (m==n) ans*=2;
}
int main()
{
	freopen("enwrap.in","r",stdin);
	freopen("enwrap.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
	random_shuffle(p+1,p+n+1);
	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++)
	for (int k=j+1;k<=n;k++)//枚举面
		if (!ok[i][j][k]) test(i,j,k);
	printf("%.6lf\n",ans);
	return 0;
}