题目描述
- 要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。
示例 1：
- 输入：
line1 = {0, 0}, {1, 0}
line2 = {1, 1}, {0, -1} - 输出： {0.5, 0}
示例 2：
- 输入：
line1 = {0, 0}, {3, 3}
line2 = {1, 1}, {2, 2} - 输出： {1, 1}
示例 3：
- 输入：
line1 = {0, 0}, {1, 1}
line2 = {1, 0}, {2, 1}
-输出： {}，两条线段没有交点
提示：
- 坐标绝对值不会超过 2^7
- 输入的坐标均是有效的二维坐标
解题思路与代码
这道题，乍一看是不是很简单，方法就是像初高中的一道数学题。让你去判断两条直线是否具有交点？
但是呢，这道题是让你去判断两条线段是否具有交点。并且，如果有多个交点，返回最小的那一个。（在多个交点中，有且只有一个交点，它的x的值最小，那么返回这个x最小的交点。如果交点的x值都相同，则返回y值最小的交点）
不要小看线段与直线的区别，就这一点区别，让整道题的难度激增。
并且，关于直线的方程式有好多种，比如一般式方程啦，点斜式方程啦，斜截式方程啦，截距式方程啦，参数式方程啦，选择用哪一个，这也是重中之重。因为这些方程式各有优缺点。选错了，你解题的步骤又可能激增，然后等于是难上加难再加难。对就是这样。
我这边，特地的选择了一种，最好理解的方式来解决这道题。也就是使用一般式方程进行求解。这种方式最大的好处就是，写出来的代码简单易懂。
并且，这道题实际上是很偏数学的，数学不好，或者说数学与代码的结合能力差，也是根本不可能做的出来的。
如果不是面试游戏公司，应该不会出这样的代数题来为难大家吧，hhhhh。
废话不多说了，开始带大家解题吧。
方法一 ： 直线的一般式方程求解
基础知识
首先我们解决这道题采用的是直线的一般式方程，也就是说形如Ax + By + C = 0；用到了这个方程的两个结论。
-
一个结论就是，如果两条直线平行，则
A1B2 = A2B1。 -
其次就是，任何直线Ax + By + C = 0 中的A，B，C，都可以用两个点的横轴坐标这么去表示：
- A = y2 - y1；
- B = x1 - x2；
- C = x2y1 - x1y2；
-
如果你对这两个结论感到疑惑了话，可以去看这个文章，去补充自己的基础知识： 直线的一般式方程
还有一个知识就是关于克莱姆法则，这个涉及到大学的线性代数中的行列式的一点基础知识。也不难。如果你想要具体了解什么是克莱姆法则的话，可以去看这篇文章去补充相关的基础知识：克莱姆法则
-
如果大家懒的看这个百度百科的克莱姆法则，你也可以看看我说的简化版的。
-
克莱姆法则（Cramer’s Rule）是一种用于求解线性方程组的方法，适用于具有唯一解的线性方程组。克莱姆法则使用行列式（determinants）来求解方程组，它的基本思想是将原线性方程组的系数矩阵通过替换列的方法，变换成相应的行列式，然后通过计算这些行列式的值来求解未知数。
-
对于一个 n 阶线性方程组，如果系数行列式不为零（即方程组具有唯一解），那么可以使用克莱姆法则求解。具体求解方法是：将系数矩阵的第 i 列替换为
方程组的右侧常数项构成的列向量，然后计算新的行列式，再将这个行列式与原系数行列式之比作为未知数 x_i 的解。 -
那么对于这道题来说，我们有4个点，也就是两条线段。我们可以把它先理解为两条直线，那么就会有两条一般式的直线方程。也就组成了一个二元的方程组。
A1x + B1y + C1 = 0; => A1x + B1y = -C1;（方程组右侧是-C1）A2x + B2y + C2 = 0; => A2x + B2y = -C2;（方程组右侧是-C2）
-
在每一个方程里只有两个未知数，所以这个二元一次方程组的系数矩阵（记作：D)为：
|A1 B1| |A2 B2| -
计算行列式的方法是主对角线（从左上到右下）的乘积 - 副对角线（从左下到右上）的乘积。所以D这个系数矩阵的值为 ：A1B2 - A2B1;
-
我们将第一列替换为常数项列向量，得到矩阵：
| -c1 b1 |
| -c2 b2 |
-
设 Dx 为这个矩阵的行列式值，即 Dx = -c1 * b2 - (-c2 * b1)。那么解 x1 = Dx / D。
-
同理，我们将第二列替换为常数项列向量，得到矩阵：
| a1 -c1 | | a2 -c2 | -
设 Dy 为这个矩阵的行列式值，即 Dy = a1 * c2 - a2 * c1。那么解 x2 = Dy / D。
-
我们可以把这组解x1，x2看做是两条直线的交点的横纵坐标，x1 = x， x2 = y，
- 所以 x = Dx/D
- 所以 y = Dy/D
好，知道这么多数学知识，就够我们去解决这道代码题的了。还是强调一下，直线的一般式方程求解是众多直线方程中最好理解的一种了。但就这一种也够复杂的了，如果不是面游戏公司，注重几何的，没必要再深究这道题的其他解法。
解题步骤
对于这道题，我们需要写这么几个函数，分别是：
- 计算方程参数ABC的函数
- 寻找当线段平行时是否存在符合题目的交点的函数
- 判断交点是否在两条线段上的函数
- 然后就是用主函数集合这么几个函数来求得最终的解。
- 我们在主函数里先这么去写逻辑，首先判断俩直线是否平行，如果平行则，调用寻
找当线段平行时是否存在符合题目的交点的函数，去找符合的点，找不到则返回空 - 其次用
计算方程参数ABC的函数去计算两天线段的一般式方程的ABC参数分别是多少，分别存储在两个double的vector中。 - 用
克莱姆法则求出可能交点，再用判断交点是否在两条线段上的函数判断交点是否在两条线段上，若在，返回交点，否则返回空 - 至此本题解完。
- 我们在主函数里先这么去写逻辑，首先判断俩直线是否平行，如果平行则，调用寻
具体实现请看代码：
class Solution {
public:
vector<double> intersection(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2) {
//由一般式方程Ax + By + C = 0 的结论可知 A = y2 - y1; B = x1 - x2; C = x2y1 - x1y2;
int A1 = end1[1] - start1[1];
int B1 = start1[0] - end1[0];
int A2 = end2[1] - start2[1];
int B2 = start2[0] - end2[0];
//如果线段平行，则去寻找是否有这样一个符合条件的点，找到则返回交点，否则返回空
if(A1 * B2 == A2 * B1) return findPointOnTheParallelLine(start1,end1,start2,end2);
//获取两条直线方程的参数ABC
vector<double> p1 = getParm(start1,end1);
vector<double> p2 = getParm(start2,end2);
//根据克莱姆法则计算可能交点(x,y)的坐标;
double x = (p2[2] * p1[1] - p1[2] * p2[1]) / (p1[0] * p2[1] - p2[0] * p1[1]);
double y = (p1[2] * p2[0] - p2[2] * p1[0]) / (p1[0] * p2[1] - p2[0] * p1[1]);
vector<double> result{x,y};
return (isIntersectionPoint(result,start1,end1) && isIntersectionPoint(result,start2,end2)) ? result : vector<double>{};
}
vector<double>findPointOnTheParallelLine(vector<int>& start1, vector<int>& end1, vector<int>& start2, vector<int>& end2){
vector<vector<double>> result;
if(isIntersectionPoint(start1,start2,end2)) result.push_back(vector<double>{double(start1[0]), double(start1[1])});
if(isIntersectionPoint(start2,start1,end1)) result.push_back(vector<double>{double(start2[0]), double(start2[1])});
if(isIntersectionPoint(end1,start2,end2)) result.push_back(vector<double>{double(end1[0]), double(end1[1])});
if(isIntersectionPoint(end2,start1,end1)) result.push_back(vector<double>{double(end2[0]), double(end2[1])});
if(result.empty()) return vector<double>{};
sort(result.begin(),result.end(),[](vector<double>& l, vector<double>& q) -> bool{return l[0] < q[0];});
return result[0];
}
vector<double> getParm(vector<int>& s, vector<int>& e){
return {double(e[1] - s[1]),double(s[0] - e[0]),double(e[0] * s[1] - s[0] * e[1])};
}
template<typename T1, typename T2, typename T3>
bool isIntersectionPoint(T1 &p, T2 &s, T3 &e){
double flag = 1e-7;
double d1 = sqrt((p[0] - s[0]) * (p[0] - s[0]) + (p[1] - s[1]) * (p[1] - s[1]));
double d2 = sqrt((p[0] - e[0]) * (p[0] - e[0]) + (p[1] - e[1]) * (p[1] - e[1]));
double d3 = sqrt((s[0] - e[0]) * (s[0] - e[0]) + (s[1] - e[1]) * (s[1] - e[1]));
return fabs(d1 + d2 - d3) <= flag;
}
};
复杂度分析
intersection() 函数：
- 时间复杂度：O(1)，因为这个函数中的所有操作都是常数时间操作，没有循环或递归。
- 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。
findPointOnTheParallelLine() 函数：
- 时间复杂度：O(1)，这个函数中的所有操作都是常数时间操作，没有循环或递归。
- 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。
getParm() 函数：
- 时间复杂度：O(1)，这个函数中的所有操作都是常数时间操作，没有循环或递归。
- 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。
isIntersectionPoint() 函数：
- 时间复杂度：O(1)，这个函数中的所有操作都是常数时间操作，没有循环或递归。
- 空间复杂度：O(1)，函数内部创建了常数个变量和容器，没有使用动态分配内存。
整个算法的时间复杂度和空间复杂度都是 O(1)，因为所有函数都具有常数时间和空间复杂度。
总结
这道题确实是一道困难题，但也是一道十分有乐趣的题。因为它很巧妙的把数学的几何知识融入到了算法题中，让我见识到了数学与算法的结合。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。