线段相交 参考算法导论P597
struct point{ double x,y; }; struct bian{ point a,b; }; double xmult(point a,point b,point c)//大于零代表a,b,c左转 { return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x); } bool OnSegment(point a,point b,point c)//a,b,c共线时有效 { return c.x>=min(a.x,b.x)&&c.x<=max(a.x,b.x)&&c.y>=min(a.y,b.y)&&c.y<=max(a.y,b.y); } bool cross(point a,point b,point c,point d){//判断ab 与cd是否相交 double d1,d2,d3,d4; d1=xmult(c,d,a); d2=xmult(c,d,b); d3=xmult(a,b,c); d4=xmult(a,b,d); if(d1*d2<0&&d3*d4<0) return 1; else if(d1==0&&OnSegment(c,d,a)) return 1; else if(d2==0&&OnSegment(c,d,b)) return 1; else if(d3==0&&OnSegment(a,b,c)) return 1; else if(d4==0&&OnSegment(a,b,d)) return 1; return 0; }
hdoj 1086