3187051_ac_30ms_4136k.cpp

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

	   }
      vol = VolumeSign( f0, v3 );
   }
   vertices = v3;
   if ( debug ) {
      PrintOut( vertices );
   }	
}
void	ConstructHull( void )
{
   tVertex  v, vnext;
   int 	    vol;
   bool	    changed;	

   v = vertices;
   do {
      vnext = v->next;
      if ( !v->mark ) {
         v->mark = PROCESSED;
	 changed = AddOne( v );
	 CleanUp();

	 if ( check ) {
	    Checks();
	 }
	 if ( debug )
            PrintOut( v );
      }
      v = vnext;
   } while ( v != vertices );
}

bool 	AddOne( tVertex p )
{
   tFace  f; 
   tEdge  e, temp;
   int 	  vol;
   bool	  vis = false;

   if ( debug ) {
   }

   f = faces;
   do {
      vol = VolumeSign( f, p );
      if ( vol < 0 ) {
	 f->visible = VISIBLE;  
	 vis = true;                      
      }
      f = f->next;
   } while ( f != faces );

   if ( !vis ) {
      p->onhull = !ONHULL;  
      return false; 
   }

   e = edges;
   do {
      temp = e->next;
      if ( e->adjface[0]->visible && e->adjface[1]->visible )
	 e->del = REMOVED;
      else if ( e->adjface[0]->visible || e->adjface[1]->visible ) 
	 e->newface = MakeConeFace( e, p );
      e = temp;
   } while ( e != edges );
   return true;
}

int  VolumeSign( tFace f, tVertex p )
{
   double  vol;
   int     voli;
   double  ax, ay, az, bx, by, bz, cx, cy, cz;

   ax = f->vertex[0]->v[X] - p->v[X];
   ay = f->vertex[0]->v[Y] - p->v[Y];
   az = f->vertex[0]->v[Z] - p->v[Z];
   bx = f->vertex[1]->v[X] - p->v[X];
   by = f->vertex[1]->v[Y] - p->v[Y];
   bz = f->vertex[1]->v[Z] - p->v[Z];
   cx = f->vertex[2]->v[X] - p->v[X];
   cy = f->vertex[2]->v[Y] - p->v[Y];
   cz = f->vertex[2]->v[Z] - p->v[Z];

   vol =   ax * (by*cz - bz*cy)+ ay * (bz*cx - bx*cz) + az * (bx*cy - by*cx);

   if      ( vol >  0.5 )  return  1;
   else if ( vol < -0.5 )  return -1;
   else                    return  0;
}
/*---------------------------------------------------------------------*/
int  Volumei( tFace f, tVertex p )
{
   double  vol;
   int     voli;
   double  ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;

   ax = f->vertex[0]->v[X] - p->v[X];
   ay = f->vertex[0]->v[Y] - p->v[Y];
   az = f->vertex[0]->v[Z] - p->v[Z];
   bx = f->vertex[1]->v[X] - p->v[X];
   by = f->vertex[1]->v[Y] - p->v[Y];
   bz = f->vertex[1]->v[Z] - p->v[Z];
   cx = f->vertex[2]->v[X] - p->v[X];
   cy = f->vertex[2]->v[Y] - p->v[Y];
   cz = f->vertex[2]->v[Z] - p->v[Z];

   vol =  (ax * (by*cz - bz*cy)  + ay * (bz*cx - bx*cz)  + az * (bx*cy - by*cx));

   if      ( vol > 0.5 )   return  1;
   else if ( vol < -0.5 )  return -1;
   else                    return  0;
}
tFace	MakeConeFace( tEdge e, tVertex p )
{
   tEdge  new_edge[2];
   tFace  new_face;
   int 	  i, j;

   for ( i=0; i < 2; ++i ) 
      if ( !( new_edge[i] = e->endpts[i]->duplicate) ) {
	 new_edge[i] = MakeNullEdge();
	 new_edge[i]->endpts[0] = e->endpts[i];
	 new_edge[i]->endpts[1] = p;
	 e->endpts[i]->duplicate = new_edge[i];
      }
   new_face = MakeNullFace();   
   new_face->edge[0] = e;
   new_face->edge[1] = new_edge[0];
   new_face->edge[2] = new_edge[1];
   MakeCcw( new_face, e, p ); 
        
   for ( i=0; i < 2; ++i )
      for ( j=0; j < 2; ++j )  
	 if ( !new_edge[i]->adjface[j] ) {
	    new_edge[i]->adjface[j] = new_face;
	    break;
	 }
        
   return new_face;
}

void	MakeCcw( tFace f, tEdge e, tVertex p )
{
   tFace  fv;  
   int    i;  
   tEdge  s;	
      
   if  ( e->adjface[0]->visible )      
        fv = e->adjface[0];
   else fv = e->adjface[1];
       
   for ( i=0; fv->vertex[i] != e->endpts[0]; ++i )   ;
   if ( fv->vertex[ (i+1) % 3 ] != e->endpts[1] ) {
      f->vertex[0] = e->endpts[1];  
      f->vertex[1] = e->endpts[0];    
   }
   else {                               
      f->vertex[0] = e->endpts[0];   
      f->vertex[1] = e->endpts[1];      
      SWAP( s, f->edge[1], f->edge[2] );
   }
   f->vertex[2] = p;
}
 
tEdge 	MakeNullEdge( void )
{
   tEdge  e;
   NEW( e, tsEdge );
   e->adjface[0] = e->adjface[1] = e->newface = NULL;
   e->endpts[0] = e->endpts[1] = NULL;
   e->del = !REMOVED;
   ADD( edges, e );
   return e;
}

tFace 	MakeNullFace( void )
{
   tFace  f;
   int    i;
   NEW( f, tsFace);
   for ( i=0; i < 3; ++i ) {
      f->edge[i] = NULL;
      f->vertex[i] = NULL;
   }
   f->visible = !VISIBLE;
   ADD( faces, f );
   return f;
}
tFace   MakeFace( tVertex v0, tVertex v1, tVertex v2, tFace fold )
{
   tFace  f;
   tEdge  e0, e1, e2;
   if( !fold ) {
     e0 = MakeNullEdge();
     e1 = MakeNullEdge();
     e2 = MakeNullEdge();
   }
   else { 
     e0 = fold->edge[2];
     e1 = fold->edge[1];
     e2 = fold->edge[0];
   }
   e0->endpts[0] = v0;              e0->endpts[1] = v1;
   e1->endpts[0] = v1;              e1->endpts[1] = v2;
   e2->endpts[0] = v2;              e2->endpts[1] = v0;

   f = MakeNullFace();
   f->edge[0]   = e0;  f->edge[1]   = e1; f->edge[2]   = e2;
   f->vertex[0] = v0;  f->vertex[1] = v1; f->vertex[2] = v2;

   e0->adjface[0] = e1->adjface[0] = e2->adjface[0] = f;
	
   return f;
}

void	CleanUp( void )
{
   CleanEdges();
   CleanFaces();
   CleanVertices();
}

void	CleanEdges( void )
{
   tEdge  e;
   tEdge  t;
   e = edges;
   do {
      if ( e->newface ) { 
	 if ( e->adjface[0]->visible )
	    e->adjface[0] = e->newface; 
	 else	e->adjface[1] = e->newface;
	 e->newface = NULL;
      }
      e = e->next;
   } while ( e != edges );
   while ( edges && edges->del ) { 
      e = edges;
      DELETE( edges, e );
   }
   e = edges->next;
   do {
      if ( e->del ) {
	 t = e;
	 e = e->next;
	 DELETE( edges, t );
      }
      else e = e->next;
   } while ( e != edges );
}
void	CleanFaces( void )
{
   tFace  f;
   tFace  t;	
	

   while ( faces && faces->visible ) { 
      f = faces;
      DELETE( faces, f );
   }
   f = faces->next;
   do {
      if ( f->visible ) {
	 t = f;
	 f = f->next;
	 DELETE( faces, t );
      }
      else f = f->next;
   } while ( f != faces );
}

void	CleanVertices( void )
{
   tEdge    e;
   tVertex  v, t;
   e = edges;
   do {
      e->endpts[0]->onhull = e->endpts[1]->onhull = ONHULL;
      e = e->next;
   } while (e != edges);
	
   while ( vertices && vertices->mark && !vertices->onhull ) { 
      v = vertices;
      DELETE( vertices, v );
   }
   v = vertices->next;
   do {
      if ( v->mark && !v->onhull ) {    
	 t = v; 
	 v = v->next;
	 DELETE( vertices, t )
      }
      else v = v->next;
   } while ( v != vertices );

   v = vertices;
   do {
      v->duplicate = NULL; 
      v->onhull = !ONHULL; 
      v = v->next;
   } while ( v != vertices );
}
bool	Collinear( tVertex a, tVertex b, tVertex c )
{
   return ( c->v[Z] - a->v[Z] ) * ( b->v[Y] - a->v[Y] ) -
         ( b->v[Z] - a->v[Z] ) * ( c->v[Y] - a->v[Y] ) == 0
      && ( b->v[Z] - a->v[Z] ) * ( c->v[X] - a->v[X] ) -
         ( b->v[X] - a->v[X] ) * ( c->v[Z] - a->v[Z] ) == 0
      && ( b->v[X] - a->v[X] ) * ( c->v[Y] - a->v[Y] ) -
         ( b->v[Y] - a->v[Y] ) * ( c->v[X] - a->v[X] ) == 0  ;
}
void	Consistency( void )
{
   register tEdge  e;
   register int    i, j;
   e = edges;
   do {
      for ( i = 0; e->adjface[0]->vertex[i] != e->endpts[0]; ++i ) ;
   
      for ( j = 0; e->adjface[1]->vertex[j] != e->endpts[0]; ++j ) ;

      if ( !( e->adjface[0]->vertex[ (i+1) % 3 ] ==
	      e->adjface[1]->vertex[ (j+2) % 3 ] ||
	      e->adjface[0]->vertex[ (i+2) % 3 ] ==
	      e->adjface[1]->vertex[ (j+1) % 3 ] )  )
	 break;
      e = e->next;
   } while ( e != edges );
}
void	Convexity( void )
{
   register tFace    f;
   register tVertex  v;
   int               vol;
   f = faces;
   do {
      v = vertices;
      do {
	 if ( v->mark ) {
	    vol = VolumeSign( f, v );
	    if ( vol < 0 )     break;
	 }
	 v = v->next;
      } while ( v != vertices );
      f = f->next;
   } while ( f != faces );

}
void	CheckEuler( int V, int E, int F ){}
void	Checks( void ){}
void	PrintOut( tVertex v ){}
void	PrintVertices( void ){}
void	PrintEdges( void ){}
void	PrintFaces( void ){}