一直线段P1P2， Q1Q2，判断其是否相交
快速排斥试验
若两线段相交，则以P1P2, Q1Q2为对角线分别作两个矩形;
如果这两个矩形相交，则两线段可能相交；
如果不相交则两线段必然不相交。
跨立试验
若P1P2跨立Q1Q2，则向量(P1−Q1), (P2−Q1)在向量(Q2−Q1)两侧。
满足(P1−Q1)×(Q2−Q1)∗(P2−Q1)×(Q2−Q1)<0。
若(P1−Q1)×(Q2−Q1)∗(P2−Q1)×(Q2−Q1)=0，说明P1或P2在直线Q1Q2上，但因为已通过快速排斥试验，所以这两线段是相交的。
故上式可改写成 (P1−Q1)×(Q2−Q1)∗(P2−Q1)×(Q2−Q1)≤0
同理，若Q1Q2跨立P1P2，则要满足(Q1−P1)×(P2−P1)∗(Q2−P1)×(P2−P1)≤0
当P1P2跨立Q1Q2且Q1Q2跨立P1P2，跨立试验成功。
（以上论述取自互联网）
struct Point{
double x,y;
}P1,P2,Q1,Q2;
double Cross(Point a, Point b, Point c)
{
return (b.x-a.x) * (c.y-a.y) - (b.y-a.y) * (c.x-a.x);
}
bool inter(point a, point b, point c, point d)
{//快速排斥
if( min(a.x, b.x) > max(c.x, d.x) || min(a.y, b.y) > max(c.y, d.y) ||
min(c.x, d.x) > max(a.x, b.x) || min(c.y, d.y) > max(a.y, b.y) )
return 0;
//跨立实验
double h, i, j, k;
h = Cross(a, b, c);
i = Cross(b, a, d);
j = Cross(d, c, a);
k = Cross(d, c, b);
return h*i<=eps && j*k<=eps;
}
当快速排斥试验与跨立实验都成功时，这两条线段相交。
