POJ 3528 hdu 3662 三维凸包模板题

一个是求三维凸包面数，一个是求三维凸包表面积，都是很裸的。

贴代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; const int MAXN=1050; 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)); } //三角形面积*2 double area(Point a,Point b,Point c){ return vlen((b-a)*(c-a)); } //四面体有向体积*6 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;i
        
         eps){ swap(P[2],P[i]); flag=false; break; } } if(flag)return; flag=true; //使前四个点不共面 for(int i=3;i
         
          eps){ 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;i
          
           eps){ dfs(i,j); break; } } } tmp=num; for(i=num=0;i