3187051_ac_30ms_4136k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define SWAP(t,x,y)	{ t = x; x = y; y = t; }
char *malloc();
#define NEW(p,type)	if ((p=(type *) malloc (sizeof(type))) == NULL) {\
				exit(0);\
			}
#define FREE(p)		if (p) { free ((char *) p); p = NULL; }


#define ADD( head, p )  if ( head )  { \
				p->next = head; \
				p->prev = head->prev; \
				head->prev = p; \
				p->prev->next = p; \
			} \
			else { \
				head = p; \
				head->next = head->prev = p; \
			}

#define DELETE( head, p ) if ( head )  { \
				if ( head == head->next ) \
					head = NULL;  \
				else if ( p == head ) \
					head = head->next; \
				p->next->prev = p->prev;  \
				p->prev->next = p->next;  \
				FREE( p ); \
			} 


/* Define vertex indices. */
#define X   0
#define Y   1
#define Z   2

/* Define structures for vertices, edges and faces */
typedef struct tVertexStructure tsVertex;
typedef tsVertex *tVertex;

typedef struct tEdgeStructure tsEdge;
typedef tsEdge *tEdge;

typedef struct tFaceStructure tsFace;
typedef tsFace *tFace;

struct tVertexStructure {
   int      v[3];
   int	    vnum;
   tEdge    duplicate;	        /* pointer to incident cone edge (or NULL) */
   bool     onhull;				/* T iff point on hull. */
   bool	    mark;				/* T iff point already processed. */
   tVertex  next, prev;
};

struct tEdgeStructure {
   tFace    adjface[2];
   tVertex  endpts[2];
   tFace    newface;            /* pointer to incident cone face. */
   bool     del;				/* T iff edge should be del. */
   tEdge    next, prev;
};

struct tFaceStructure {
   tEdge    edge[3];
   tVertex  vertex[3];
   bool	    visible;	        /* T iff face visible from new point. */
   tFace    next, prev;
};
struct point3{
	int x,y,z;
	bool operator < (const point3& that) const{
		if (x<that.x) return true;
		if (x>that.x) return false;
		if (y<that.y) return true;
		if (y>that.y) return false;
		return z<that.z;
	}
}myp[1000+5];
int used[1000000];
struct face{
	int k1,k2,k3;
}myf[1000000];
int fflag;
#define ONHULL   	true
#define REMOVED  	true
#define VISIBLE  	true
#define PROCESSED	true
#define SAFE		100000		/* Range of safe coord values. */
tVertex vertices = NULL;
tEdge edges    	 = NULL;
tFace faces    	 = NULL;
bool debug = false;
bool check = false;
/* Function declarations */
tVertex MakeNullVertex( void );
void    ReadVertices();
void    Print( void );
void    SubVec( int a[3], int b[3], int c[3]);
void    DoubleTriangle( void );
void    ConstructHull( void );
bool	AddOne( tVertex p );
int     VolumeSign(tFace f, tVertex p);
int 	Volumei( tFace f, tVertex p );
tFace	MakeConeFace( tEdge e, tVertex p );
void    MakeCcw( tFace f, tEdge e, tVertex p );
tEdge   MakeNullEdge( void );
tFace   MakeNullFace( void );
tFace   MakeFace( tVertex v0, tVertex v1, tVertex v2, tFace f );
void    CleanUp( void );
void    CleanEdges( void );
void    CleanFaces( void );
void    CleanVertices( void );
bool	Collinear( tVertex a, tVertex b, tVertex c );
void    CheckEuler(int V, int E, int F );
void    Checks( void );
void	Consistency( void );
void	Convexity( void );
void	PrintOut( tVertex v );
void	PrintVertices( void );
void	PrintEdges( void );
void	PrintFaces( void );
int ans;
int nnn;
double area;
int main( int argc, char *argv[] )
{
//	int T,tcase=0;
//	scanf("%d",&T);
//	while(T--)
	{
		vertices = NULL;
		edges  	 = NULL;
		faces  	 = NULL;
		debug = false;
		check = false;
        ans=0;
		fflag=0;
		area = 0;
		scanf("%d",&nnn);
		ReadVertices();
		if(nnn < 3)
		{
			puts("0.000");
			return 0;
		}
		if (fflag==0){
			DoubleTriangle();
			ConstructHull();
			Print();
		}
	//	if (fflag==1) area=0;
		//printf("%d\n",ans);
		printf("%.3lf\n",area);
	}
	return 0;
}

tVertex	MakeNullVertex( void )
{
   tVertex  v;
   NEW( v, tsVertex );
   v->duplicate = NULL;
   v->onhull = !ONHULL;
   v->mark = !PROCESSED;
   ADD( vertices, v );
   return v;
}
void ReadVertices()
{
   tVertex  v;
   int x,y,z;
   int i,n;
       for(i=0;i<nnn;i++){
		   scanf("%d%d%d",&myp[i].x,&myp[i].y,&myp[i].z);
	   }
	   sort(myp,myp+nnn);
	   n=nnn;  nnn=0;
	   for(i=0;i<n;i++)
		   if (i>0 && myp[i].x==myp[i-1].x && myp[i].y==myp[i-1].y && myp[i].z==myp[i-1].z) continue;
		   else myp[nnn++]=myp[i];
	  if (nnn<4){
		   fflag=1;
		   return ;
	   }
	   for(i=0;i<nnn;i++){
		    v = MakeNullVertex();
	        v->v[X] = myp[i].x;
	 		v->v[Y] = myp[i].y;
			v->v[Z] = myp[i].z;
		    v->vnum = i;
	   }
}

//【计算dot product U·V】
int dmult(point3 u,point3 v){ 
	return u.x*v.x+u.y*v.y+u.z*v.z;
}
//【矢量差 U-V】
point3 subt(point3 u,point3 v){
	point3 ret;
	ret.x=u.x-v.x;		ret.y=u.y-v.y;		ret.z=u.z-v.z;
	return ret;
}
//【计算cross product UxV】
point3 xmult(point3 u,point3 v){
	point3 ret;
	ret.x=u.y*v.z-v.y*u.z;
	ret.y=u.z*v.x-u.x*v.z;
	ret.z=u.x*v.y-u.y*v.x;
	return ret;
}

//【取平面法向量】
point3 pvec(point3 a,point3 b,point3 c){return xmult(subt(a,b),subt(b,c));}

//【判四点共面】
int dots_onplane(point3 a,point3 b,point3 c,point3 d){
	return dmult(pvec(a,b,c),subt(d,a));
}

double getarea(point3 p1,point3 p2,point3 p3)
{
	double a = sqrt((double)((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z)));
	double b = sqrt((double)((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y)+(p1.z-p3.z)*(p1.z-p3.z)));
	double c = sqrt((double)((p3.x-p2.x)*(p3.x-p2.x)+(p3.y-p2.y)*(p3.y-p2.y)+(p3.z-p2.z)*(p3.z-p2.z)));
	double p = (a+b+c)/2.0;
	return sqrt(p*(p-a)*(p-b)*(p-c));
}

void	Print( void )
{
   tVertex  v;
   tEdge    e;
   tFace    f;
   int xmin, ymin, xmax, ymax;
   int a[3], b[3];  
   int fcnt,i,j;
   int 	V = 0, E = 0 , F = 0;
   v = vertices;
   xmin = xmax = v->v[X];
   do {
      if( v->v[X] > xmax ) xmax = v->v[X];
      else
	 if( v->v[X] < xmin ) xmin = v->v[X];
      v = v->next;
   } while ( v != vertices );
	
   v = vertices;
   ymin = ymax = v->v[Y];
   do {
      if( v->v[Y] > ymax ) ymax = v->v[Y];
      else
	 if( v->v[Y] < ymin ) ymin = v->v[Y];
      v = v->next;
   } while ( v != vertices );
	
   v = vertices;
   do {                                 
      if( v->mark ) V++;           
      v = v->next;
   } while ( v != vertices );
   do {                                 
      v = v->next;
   } while ( v != vertices );
	
   f = faces;
   do {
      ++F;                              
      f  = f ->next;
   } while ( f  != faces );
   do {           
      SubVec( f->vertex[1]->v, f->vertex[0]->v, a );
      SubVec( f->vertex[2]->v, f->vertex[1]->v, b );	  
      f = f->next;
   } while ( f != faces );

   fcnt=0;
   do {
        myf[fcnt].k1=f->vertex[0]->vnum;
		myf[fcnt].k2=f->vertex[1]->vnum;
        myf[fcnt].k3=f->vertex[2]->vnum;
		area += getarea(myp[myf[fcnt].k1],myp[myf[fcnt].k2],myp[myf[fcnt].k3]);
	//	printf("         %d %d %d\n",myf[fcnt].k1,myf[fcnt].k2,myf[fcnt].k3);
		fcnt++;
      f = f->next;
   } while ( f != faces );
 //  printf("fcnt=%d\n",fcnt);
   memset(used,1,sizeof(used));
   ans=0;
   for(i=0;i<fcnt;i++) if (used[i]){
	   ans++;
	   for(j=i+1;j<fcnt;j++) 
		   if (!dots_onplane(myp[myf[i].k1],myp[myf[i].k2],myp[myf[i].k3],myp[myf[j].k1]) &&
			   !dots_onplane(myp[myf[i].k1],myp[myf[i].k2],myp[myf[i].k3],myp[myf[j].k2]) &&
               !dots_onplane(myp[myf[i].k1],myp[myf[i].k2],myp[myf[i].k3],myp[myf[j].k3])){
			   used[j]=0;
		   }
   }
   e = edges;
   do {
      E++;
      e = e->next;
   } while ( e != edges );
   check = true;
}

void    SubVec( int a[3], int b[3], int c[3])
{
   int  i;
   for( i=0; i < 2; i++ )
      c[i] = a[i] - b[i];
}
void    DoubleTriangle( void )
{
   tVertex  v0, v1, v2, v3, t;
   tFace    f0, f1 = NULL;
   tEdge    e0, e1, e2, s;
   int      vol;
	
   v0 = vertices;
   while ( Collinear( v0, v0->next, v0->next->next ) )
	   if ( ( v0 = v0->next ) == vertices ){
		   fflag=1;
		   
		 return;
	   }
   v1 = v0->next;
   v2 = v1->next;
	
   v0->mark = PROCESSED;
   v1->mark = PROCESSED;
   v2->mark = PROCESSED;
   
   f0 = MakeFace( v0, v1, v2, f1 );
   f1 = MakeFace( v2, v1, v0, f0 );

   f0->edge[0]->adjface[1] = f1;
   f0->edge[1]->adjface[1] = f1;
   f0->edge[2]->adjface[1] = f1;
   f1->edge[0]->adjface[1] = f0;
   f1->edge[1]->adjface[1] = f0;
   f1->edge[2]->adjface[1] = f0;
	
   v3 = v2->next;
   vol = VolumeSign( f0, v3 );
   while ( !vol )   {
	   if ( ( v3 = v3->next ) == v0 ) {
		     fflag=1;
		 
		   return;