判断两条线段相交

Tip ：注意是线段相交~

算法牢骚:主要是看错题....把题目看难了...感觉脑补了一下线段相交的知识,but在ACM里木有找到讲解比较好一点的（也有可能我孤陋寡闻吧）...

核心步骤：

1.快速排斥（好像很高级....）

2.跨立实验（好像更高级???来人，加BUFF）

前提：线段AB，线段CD，矩形A，矩形B，直线AB

快速排斥就是以线段AB作为矩形A的对角线，线段CD作为矩形B的对角线，看两个矩阵A,B是否可以相交

首先你得让矩形A,B两个矩形相交!!!!!( WHY ?请看跨立实验)

跨立实验：

假设我们讨论得是直线AB（无限延伸）和线段CD，问两条线是否相交?

只要线段CD的两个端点分别在直线AB的两侧   

那么就可以说直线AB和线段CD相交!!!

（不要嫌弃图片....画画水平一年级）

如果直接用跨立实验来判断线段AB和线段CD是否相交...会出现这种尴尬的情况：

黑人问号?

如何防止这种尴尬情况?

快速排斥就是干这事滴~~

细节：

我们回想一下..线段AB和直线AB有什么区别?

答案是 线段AB有长度限制阿...

那如果锁定一个区域呢?

实现:

跨立实验采用了两点式而没有采用叉乘 ... 算是一种优化?

bool judge(Line p1,Line p2){

    if(!(min(x1,x2) <= max(x3,x4) && min(y3,y4) <= max(y1,y2) && min(x3,x4) <= max(x1,x2) && min(y1,y2) <= max(y3,y4)))
      return false;

    double fc = (y3-y1) * (x2-x1) - (x3-x1) *(y2-y1);
    double fd = (y4-y1) * (x2-x1) - (x4-x1) *(y2-y1);
 
    if(fc * fd > 0)    return false;

    return true;

}