给定由一个三维向量 INLINECODE6c2bf068 表示的两条线段，其中每条线段 INLINECODE58dc80a0 由存储在 INLINECODEd0ec92a6 和 INLINECODE2b137472 中的端点定义（每个端点包含 2 个整数），我们的任务是确定这两条线段是否彼此相交。
示例：
> 输入：points[][][] = [ [[1, 1], [10, 1]] , [[1, 2], [10, 2]] ]
> 输出：No
> 解释：给定的线段彼此平行。
> !1
> 输入：points[][][] = [ [[10, 0], [0, 10]] , [[0, 0], [10, 10]] ]
> 输出：Yes
> 解释：给定的线段互为镜像并在中点相交。
> !2
我们要利用下面的方向概念来解决这个问题。
三个有序点的方向
> 平面上有序三元组点的方向可以是：
>
> – 逆时针
> – 顺时针
> – 共线
>
> 下图展示了 三种不同的可能方向：
>
> !image
>
> 如果 的方向是共线，那么 的方向也是共线。
> 如果 的方向是顺时针，那么 的方向就是逆时针，反之亦然。
利用线的方向 – O(1) 时间和 O(1) 空间
> 我们的核心思路是利用线的方向来确定它们是否相交。当且仅当满足以下两个条件之一时，两条线段 [p1, q1] 和 [p2, q2] 相交：
>
> 1. 一般情况：–
>
> – [p1, q1, p2] 和 [p1, q1, q2] 拥有不同的方向。
> – [p2, q2, p1] 和 [p2, q2, q1] 拥有不同的方向。
>
> 下图包含了一般情况的示例：
> !image
>
> 2. 特殊情况：
>
> – [p1, q1, p2]、[p1, q1, q2]、[p2, q2, p1] 和 [p2, q2, q1] 全部共线。
> – [p1, q1] 和 [p2, q2] 的 x 轴投影相交。
> – [p1, q1] 和 [p2, q2] 的 y 轴投影相交。
>
> 下图包含特殊情况下的示例：
> !image
方法：
> 我们的思路是首先找到分析一般情况和特殊情况所需的四个方向。我们要讨论了一种在文章“3个有序点的方向”中寻找 3 个有序点方向的方法。此后，检查一般情况，如果两个条件都为真，则返回 true，否则检查特殊情况。现在，对于特殊情况，点必须是共线的，并且点应该在线段上。要检查点是否位于线段上，请检查该点是否位于 x 和 y 坐标的最大值和最小值之间。
C++
`
#include
using namespace std;
// 检查点 q 是否位于线段 ‘pr‘ 上的函数
bool onSegment(vector& p, vector& q, vector& r) {
return (q[0] = min(p[0], r[0]) &&
q[1] = min(p[1], r[1]));
}
// 查找有序三元组 的方向的函数
// 0 --> p, q 和 r 共线
// 1 --> 顺时针
// 2 --> 逆时针
int orientation(vector& p, vector& q, vector& r) {
int val = (q[1] - p[1]) * (r[0] - q[0]) -
(q[0] - p[0]) * (r[1] - q[1]);
// 共线
if (val == 0) return 0;
// 顺时针或逆时针
// 1 代表顺时针，2 代表逆时针
return (val > 0) ? 1 : 2;
}
// 检查两条线段是否相交的函数
bool doIntersect(vector<vector<vector>>& points) {
// 找到分析一般情况和特殊情况所需的四个方向
int o1 = orientation(points[0][0], points[0][1], points[1][0]);
int o2 = orientation(points[0][0], points[0][1], points[1][1]);
int o3 = orientation(points[1][0], points[1][1], points[0][0]);
int o4 = orientation(points[1][0], points[1][1], points[0][1]);
// 一般情况
if (o1 != o2 && o3 != o4)
return true;
// 特殊情况
// p1, q1 和 p2 共线且 p2 位于线段 p1q1 上
if (o1 == 0 &&
onSegment(points[0][0], points[1][0], points[0][1])) return true;
// p1, q1 和 q2 共线且 q2 位于线段 p1q1 上
if (o2 == 0 &&
onSegment(points[0][0], points[1][1], points[0][1])) return true;
// p2, q2 和 p1 共线且 p1 位于线段 p2q2 上
if (o3 == 0 &&
onSegment(points[1][0], points[0][0], points[1][1])) return true;
// p2, q2 和 q1 共线且 q1 位于线段 p2q2 上
if (o4 == 0 &&
onSegment(points[1][0], points[0][1], points[1][1])) return true;
return false;
}
// 主函数用于测试
int main() {
// 示例 1
vector<vector<vector>> points1 = {{{1, 1}, {10, 1}}, {{1, 2}, {10, 2}}};
if (doIntersect(points1)) {
cout << "Yes
";
} else {
cout << "No
";
}
// 示例 2
vector<vector<vector>> points2 = {{{10, 0}, {0, 10}}, {{0, 0}, {10, 10}}};
if (doIntersect(points2)) {
cout << "Yes
";
} else {
cout << "No
";
}
return 0;
}