判断两线段是否相交

算法原理：黑书597页

基础习题: UVA10902

typedef double db;

//快速矩阵排除
inline bool fast(db x1,db y1,db x2,db y2,db x3,db y3,db x4,db y4){
    return (max(x1,x2)>=min(x3,x4)&&max(x3,x4)>=min(x1,x2)&&max(y1,y2)>=min(y3,y4)&&max(y3,y4)>=min(y1,y2));
}

//求矢量积
inline db cross_product(db x1,db y1,db x2,db y2){
    return x1*y2-x2*y1;
}

//跨立实验*2
inline bool cross(db x1,db y1,db x2,db y2,db x3,db y3,db x4,db y4){
    db a,b,c,d;
    a=cross_product(x3-x1,y3-y1,x2-x1,y2-y1);
    b=cross_product(x4-x1,y4-y1,x2-x1,y2-y1);
    c=cross_product(x1-x3,y1-y3,x4-x3,y4-y3);
    d=cross_product(x2-x3,y2-y3,x4-x3,y4-y3);
    return (a>0&&b<0||a<0&&b>0)&&(c>0&&d<0||c<0&&d>0);
}

//判断两条线段是否相交
inline bool segmentcross(db x1,db y1,db x2,db y2,db x3,db y3,db x4,db y4){
    if (fast(x1,y1,x2,y2,x3,y3,x4,y4))
        if (cross(x1,y1,x2,y2,x3,y3,x4,y4))
            return 1;
    return 0;
}