包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

				#include 
				#include 
				#include 
				using namespace std;
				
				//NOJ 线段相交
				/*
				输入：
				1234567890123456 9876543210987654
				1234567890123457 9876543210987655
				1234567890123457 9876543210987655
				1234567890123454 9876543210987652
				
				1 0 0 1 0 0 1 1
				
				0 1 2 1 1 0 1 2
				
				1 1 2 2 3 3 4 4
				
				输出：
				no 
				yes
				yes
				no
				*/
				
				typedef struct  POINT  
				{  
				public:  
				    double  x,y;  
				}POINT;  
				 
				typedef  struct LINESEG  
				{  
				     POINT s,e;  
				}LINESEG; 
				 
				int dblcmp(double d)
				{
					if(fabs(d)						return 0;
					return (d>0)?1:-1;
				}
				double  max(double  a,double  b)  
				{  
				     return  a>b?a:b;  
				}  
				double  min(double  a,double  b)  
				{  
				     return  a				}  
				double  multiply(POINT  sp,POINT  ep,POINT  op)  
				{  //向量叉积
				    return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));              
				}  
				bool  online(LINESEG  l,POINT  p)  
				{  
				    return(  (multiply(l.e,p,l.s)==0)  &&(  (  (p.x-l.s.x)*(p.x-l.e.x)				}  
				  
				bool  intersect(LINESEG  u,LINESEG  v)  
				{  
				    return   
				//排斥试验
						(max(v.s.x,v.e.x)>=min(u.s.x,u.e.x))&&  
				     (max(u.s.y,u.e.y)>=min(v.s.y,v.e.y))&&  
				       (max(v.s.y,v.e.y)>=min(u.s.y,u.e.y))&&
				//判断是否相交
				//使用有向面积概念
				      ((dblcmp(multiply(u.s,v.s,v.e))^dblcmp(multiply(u.e,v.s,v.e)))==-2)&&                 
				       ((dblcmp(multiply(v.s,u.s,u.e))^dblcmp(multiply(v.e,u.s,u.e)))==-2);  
				}
				
				int main()
				{
				    LINESEG L1,L2;
					float   x   =   cos(0.0);
				    while(cin>>L1.s.x>>L1.s.y>>L1.e.x>>L1.e.y>>L2.s.x>>L2.s.y>>L2.e.x>>L2.e.y)
				    {
				        if(intersect(L1,L2)) cout				        else cout				    }
				    
				    return 0;
				}