一.叉積

   設 a(x1,y1), b(x2,y2)
二維：a x b=x1*y2-x2*y1

   設p0(x0,y0), p1(x1,y1) ,p2(x2,y2), p3(x3,y3)
  < p0p1>= (p1-p0) =(x1-x0,y1-y0);
   <p2p3>= (p3-p2) =(x3-x2,y3-y2);
   <p0p1> x <p2p3> =(p1-p0) x (p3-p2) = (x1-x0)*(y3-y2)- (x3-x2)* (y1-y0); 

   (p1-p0) x (p3-p2)結果的意義:

   正: <p0p1>在<p2,p3>順時針(0,pi)內

   負: <p0p1>在<p2,p3>逆時針(0,pi)內

   0 : <p0p1>, <p2p3>共線,夾角為0或pi

double xmult(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

   可用于判p2與<p0 p1>的關系

 

double xmult(point p0,point p1,point p2,point p3){
    return (p1.x-p0.x)*(p3.y-p2.y)-(p3.x-p2.x)*(p1.y-p0.y);
}

   可用于判<p0p1>, <p2p3>位置關系

double xmult(line u,line v){
    return (u.b.x-u.a.x)*(v.b.y-v.a.y)-(v.b.x-v.a.x)*(u.b.y-u.a.y);
}

//計算兩直線交點,注意事先判斷直線是否平行!
point intersection(line u,line v){
    point ret=u.a;
    double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
            /((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
    ret.x+=(u.b.x-u.a.x)*t;
    ret.y+=(u.b.y-u.a.y)*t;
    return ret;
}

int relat_and_intersection(line u,line v,point &ret)
{
    /**//*
    LINE 重合
    NONE 平行
    INTERSECT 相交并返回交點
    */
    double a1,b1,c1,a2,b2,c2;
    //系數
    a1=u.a.y-u.b.y;
    b1=-(u.a.x-u.b.x);
    c1=u.a.x*u.b.y-u.a.y*u.b.x;

    a2=v.a.y-v.b.y;
    b2=-(v.a.x-v.b.x);
    c2=v.a.x*v.b.y-v.a.y*v.b.x;

    if(fabs(a1*b2-a2*b1)<eps)
    {
        if( fabs(a1*c2-a2*c1)<eps && fabs(b1*c2-b2*c1)<eps )
            return LINE;
        else return NONE;
    }
    else 
    {
        point ret;
        ret.x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
        ret.y=(a2*c1-a1*c2)/(a1*b2-a2*b1);
        return INTERSECT;
    }
}