noj 线段相交.txt

POJ上一些计算几何题的代码………………

#include <stdio.h>
#include <iostream>
#include <math.h>
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)<0.0000001)
		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<b?a:b;  
}  
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)<=0  )&&(  (p.y-l.s.y)*(p.y-l.e.y)<=0  )  )  );  
}  
  
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<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    
    return 0;
}