在讲解之前，先认识下“向量叉积”的概念：
如图，对于给定的向量AB与向量AC，我们如何判断AB是在AC顺时针方向还是逆时针方向呢？（如图所示，AB在AC逆时针方向，同时，AC在AB的顺时针方向）
假设向量AB坐标为（x1，y1），向量AC坐标为（x2，y2），
则规定“向量叉积”为：x1 * y2 - y1 * x2
“向量叉积”的意义是：
若为正数，则AB在AC的顺时针方向；
若为负数，则AB在AC的逆时针方向；
若为0，则AB与AC共线。
现在可以回到我们的问题，如何判断给定的两条线段是否相交呢？
如图，AB与CD相交，以AB，CD为对角线做四边形，我们可以得出AC，AD在AB的两侧；CA，CB在CD的两侧，但是这个结论不是判断相交的充要条件，只需要加一个条件就可以成为充要条件，这可以由数学证明，直接看代码。
[cpp] view plain copy print ? #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<cmath> #include<algorithm> using namespace std; struct Node { double x, y; }; /* 求出向量AB与向量AC的差积,返回0代表共线 */ double cross(Node A, Node B, Node C) { return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y); } /* 判断线段AB与线段CD是否相交，相交返回true */ bool intersect(Node A, Node B, Node C, Node D) { if (min(A.x, B.x) <= max(C.x, D.x) && min(C.x, D.x) <= max(A.x, B.x) && min(A.y, B.y) <= max(C.y, D.y) && min(C.y, D.y) <= max(A.y, B.y) && cross(A, B, C)*cross(A, B, D) < 0 &&//小于0表示在两侧，而不是同侧 cross(C, D, A)*cross(C, D, B) < 0) return true; return false; } int main() { return 0; }
