#include #include #include #include #include #define eps 1e-7 #define MAXV 310 using namespace std; struct pt { double x, y, z; pt(){} pt(double _x, double _y, double _z): x(_x), y(_y), z(_z){} pt operator - (const pt p1){return pt(x - p1.x, y - p1.y, z - p1.z);} pt operator * (pt p){return pt(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);} //²æ³Ë double operator ^ (pt p){return x*p.x+y*p.y+z*p.z;} //µã³Ë } P[MAXV]; struct fac { int a, b, c; bool ok; } add, F[MAXV*4]; int mark[MAXV*4]; int n, cnt; int to[MAXV][MAXV]; int fa[MAXV*4]; void dfs(int, int); double vlen(pt a){return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);} double area(pt a, pt b, pt c){return vlen((b-a)*(c-a));} double ptof(pt &p, fac &f) { pt m = P[f.b]-P[f.a], n = P[f.c]-P[f.a], t = p-P[f.a]; return (m * n) ^ t; } void deal(int p, int a, int b) { int f = to[a][b]; if (F[f].ok) { if (ptof(P[p], F[f]) > eps) dfs(p, f); else { add.a = b, add.b = a, add.c = p, add.ok = 1; to[p][b] = to[a][p] = to[b][a] = cnt; F[cnt++] = add; } } } void dfs(int p, int cur) { F[cur].ok = 0; deal(p, F[cur].b, F[cur].a); deal(p, F[cur].c, F[cur].b); deal(p, F[cur].a, F[cur].c); } int isin(pt p,pt p0,pt p1,pt p2) { pt aa,bb,cc; aa=p1-p0; bb=p2-p0; cc=p-p0; double k1=aa.x*bb.y*cc.z+aa.y*bb.z*cc.x+bb.x*cc.y*aa.z-(aa.z*bb.y*cc.x+aa.y*bb.x*cc.z+bb.z*cc.y*aa.x); double k2=(aa.z*bb.y*cc.x+aa.y*bb.x*cc.z+bb.z*cc.y*aa.x); if(fabs(k1) 0) swap(add.b, add.c); to[add.a][add.b] = to[add.b][add.c] = to[add.c][add.a] = cnt; F[cnt++] = add; } for (i = 4; i < n; i++) { for (j = 0; j < cnt; j++) { if (F[j].ok && ptof(P[i], F[j]) > eps) { dfs(i, j); break; } } } /*for (i = 0; i < cnt; i++) ret += F[i].ok * area(P[F[i].a], P[F[i].b], P[F[i].c]);*/ for(i=0;ieps){ tmp=P[i]; P[i]=P[2]; P[2]=tmp; flag=1; break; } } for(i=3;i