计算几何

https://blog.csdn.net/nike0good/article/details/77102473
https://www.cnblogs.com/Running-Time/p/4900553.html
poj2074直线交：https://ideone.com/ep3JVj

double Cross(Point p1,Point p2,Point p3,Point p4){    
    return (p2.x-p1.x)*(p4.y-p3.y) - (p2.y-p1.y)*(p4.x-p3.x);
}
double Area(Point p1,Point p2,Point p3){    
    return Cross(p1,p2,p1,p3);
}
double fArea(Point p1,Point p2,Point p3){    
    return fabs(Area(p1,p2,p3));
}
bool Meet(Point p1,Point p2,Point p3,Point p4){    
    return max(min(p1.x,p2.x),min(p3.x,p4.x)) <= min(max(p1.x,p2.x),max(p3.x,p4.x))        
    && max(min(p1.y,p2.y),min(p3.y,p4.y)) <= min(max(p1.y,p2.y),max(p3.y,p4.y))        
    && sgn(Cross(p3,p2,p3,p4) * Cross(p3,p4,p3,p1)) >= 0        
    && sgn(Cross(p1,p4,p1,p2) * Cross(p1,p2,p1,p3)) >= 0;
}
Point Inter(Point p1,Point p2,Point p3,Point p4){    
    double k = fArea(p1,p2,p3) / fArea(p1,p2,p4);    
    return Point((p3.x + k*p4.x)/(1+k),(p3.y + k*p4.y)/(1+k));
}

Point Inter(Point p1,Point p2,Point p3,Point p4){
    double s1 = fArea(p1,p2,p3) , s2 = fArea(p1,p2,p4);
    return Point((p4.x*s1+p3.x*s2)/(s1+s2),(p4.y*s1+p3.y*s2)/(s1+s2));
}