HDU4273 Rescue（2012 ACM/ICPC Asia Regional Changchun Online）(一)

三维凸包，贴模板过的，不解释……

[cpp]
#include
#include
#include
#include
#include
using namespace std;

const int MAXN=1001;
const int N = 500;
const double EPS=1e-8;

int g[MAXN][MAXN];

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 *(Point p){//叉乘
return Point(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);
}
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.x-a.x)*(c.z-a.z)-(b.z-a.z)*(c.x-a.x)),(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}

double area(Point a,Point b,Point c){//三角形面积*2
return vlen((b-a)*(c-a));
}

double volume(Point a,Point b,Point c,Point d){//四面体有向体积*6
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){