#include #include #include #include #include using namespace std; const int MAXN=550; const double eps=1e-8; struct Point { double x,y,z; Point(){} Point(double xx,double yy,double zz):x(xx),y(yy),z(zz){} Point operator -(const Point p1) { return Point(x-p1.x,y-p1.y,z-p1.z); } Point operator +(const Point p1) { return Point(x+p1.x,y+p1.y,z+p1.z); } Point operator *(const Point p) { return Point(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x); } Point operator *(double d) { return Point(x*d,y*d,z*d); } Point operator / (double d) { return Point(x/d,y/d,z/d); } double operator ^(Point p) { return (x*p.x+y*p.y+z*p.z); } }; struct CH3D { struct face { int a,b,c; bool ok; }; int n; Point P[MAXN]; int num; face F[8*MAXN]; int g[MAXN][MAXN]; double vlen(Point a) { return sqrt(a.x*a.x+a.y*a.y+a.z*a.z); } Point cross(const Point &a,const Point &b,const Point &c) { return Point((b.y-a.y)*(c.z-a.z)-(b.z-a.z)*(c.y-a.y), (b.z-a.z)*(c.x-a.x)-(b.x-a.x)*(c.z-a.z), (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x) ); } double area(Point a,Point b,Point c) { return vlen((b-a)*(c-a)); } double volume(Point a,Point b,Point c,Point d) { return (b-a)*(c-a)^(d-a); } double dblcmp(Point &p,face &f) { Point m=P[f.b]-P[f.a]; Point n=P[f.c]-P[f.a]; Point t=p-P[f.a]; return (m*n)^t; } void deal(int p,int a,int b) { int f=g[a][b]; face add; if(F[f].ok) { if(dblcmp(P[p],F[f])>eps) dfs(p,f); else { add.a=b; add.b=a; add.c=p; add.ok=true; g[p][b]=g[a][p]=g[b][a]=num; F[num++]=add; } } } void dfs(int p,int now) { F[now].ok=0; deal(p,F[now].b,F[now].a); deal(p,F[now].c,F[now].b); deal(p,F[now].a,F[now].c); } bool same(int s,int t) { Point &a=P[F[s].a]; Point &b=P[F[s].b]; Point &c=P[F[s].c]; return fabs(volume(a,b,c,P[F[t].a]))eps) { swap(P[1],P[i]); flag=false; break; } } if(flag)return; flag=true; for(i=2;ieps) { swap(P[2],P[i]); flag=false; break; } } if(flag)return; flag=true; for(int i=3;ieps) { swap(P[3],P[i]); flag=false; break; } } if(flag)return; for(i=0;i<4;i++) { add.a=(i+1)%4; add.b=(i+2)%4; add.c=(i+3)%4; add.ok=true; if(dblcmp(P[i],add)>0)swap(add.b,add.c); g[add.a][add.b]=g[add.b][add.c]=g[add.c][add.a]=num; F[num++]=add; } for(i=4;ieps) { dfs(i,j); break; } } } tmp=num; for(i=num=0;i