我在笛卡尔平面上有N不同的线。由于直线的斜率截距形式为y = mx + c，因此给出了这些直线的斜率和y截距。我必须找到任意两条线的最底部交点的y坐标。
我在C++中实现了一个O(N^2)解决方案，这是一种蛮力方法，对于N = 10^5来说太慢了。这是我的代码：
int main() {
int n;
cin >> n;
vector<pair<int, int>> lines(n);
for (int i = 0; i < n; ++i) {
int slope, y_intercept;
cin >> slope >> y_intercept;
lines[i].first = slope;
lines[i].second = y_intercept;
}
double min_y = 1e9;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (lines[i].first ==
lines[j].first) // since lines are distinct, two lines with same slope will never intersect
continue;
double x = (double) (lines[j].second - lines[i].second) / (lines[i].first - lines[j].first); //x-coordinate of intersection point
double y = lines[i].first * x + lines[i].second; //y-coordinate of intersection point
min_y = min(y, min_y);
}
}
cout << min_y << endl;
}
如何有效地解决这个问题？
如果您正在考虑通过线性规划(LP(来解决这个问题，那么它可以有效地完成，因为最小化或最大化目标函数的解决方案总是位于约束方程的交集中。我将向您展示如何将此问题建模为最大化LP。假设你有N=2个一阶方程要考虑：
y = 2x + 3
y = -4x + 7
然后你会把你的单纯形表设置成这样：
x0 x1 x2 x3 b
-2 1 1 0 3
4 1 0 1 7
其中，行x0表示原始一阶函数中"x"的系数的否定，x1表示"y"的系数，其通常为+1，x2和x3表示维度N乘以N的单位矩阵(它们是松弛变量(，b表示理想项的值。在这种情况下，约束受到<=操作人员
现在，目标函数应该是：
x0 x1 x2 x3
1 1 0 0
为了解决这个LP，你可以使用"单纯形"算法，它通常是有效的。
此外，结果将是一个数组，表示分配给每个变量的值。在这种情况下，解决方案是：
x0 x1 x2 x3
0.6666666667 4.3333333333 0.0 0.0
对(x0，x1(表示您要查找的点，其中x0是它的x坐标，x1是它的y坐标。你可以得到其他不同的结果，例如，不可能存在任何解决方案，你可以在乔治·丹齐格的《线性规划与扩展》等大量书籍中找到更多。
请记住，单纯形算法仅适用于X0、x1、…的正值。。。，xn。这意味着在应用单纯形之前，您必须确保您正在寻找的最佳点不在可行区域之外。
编辑2:我相信，在O(N(中，通过在每个函数的独立项上添加一个大因子，将原始函数转移到一个新的位置，可以很容易地使问题可行。查看我在下面的评论。(第3版：这意味着它不会适用于所有可能的场景，尽管它很容易实现。如果你想对任何可能的场景给出确切的答案，请查看以下关于如何将不可行象限转换为可行象限的解释(
编辑3：解决这个问题的更好方法是，即使最小点在x或y的负侧，也能精确地推断出它：将其他3个都转换到象限1。
考虑以下通用一阶函数模板：
f(x) = mx + k
考虑以下通用笛卡尔平面点模板：
p = (p0, p1)
将函数和点从y负象限转换为y正象限：
y_negative_to_y_positive( f(x) ) = -mx - k
y_negative_to_y_positive( p ) = (p0, -p1)
将函数和点从x负象限转换为x正象限：
x_negative_to_x_positive( f(x) ) = -mx + k
x_negative_to_x_positive( p ) = (-p0, p1)
总结：
quadrant sign of corresponding (x, y) converting f(x) or p to Q1
Quadrant 1 (+, +) f(x)
Quadrant 2 (-, +) x_negative_to_x_positive( f(x) )
Quadrant 3 (-, -) y_negative_to_y_positive( x_negative_to_x_positive( f(x) ) )
Quadrant 4 (+, -) y_negative_to_y_positive( f(x) )
现在将象限2、3和4中的函数转换为象限1。运行单纯形4次，一次基于原始象限1，另一次基于转换后的象限2、3和4。对于源自y负象限的情况，您需要将单纯形建模为具有负松弛变量的最小化实例，这将使您的约束变为>=格式。我将把如何基于最小化任务对同一问题建模的细节留给你。一旦你有了每个象限的结果，你手头最多有4个点(因为你可能会发现，例如，在特定的象限上没有点(。将它们中的每一个转换回其原始象限，以与原始转换类似的方式返回。
现在，你可以自由地将这4个点相互比较，并决定哪一个是你需要的。
编辑1:
- 注意，一阶函数的数量N可以随心所欲地大
- 解决这个问题的其他方法可能会更好
- 编辑3：检查单纯形的复杂性。在一般情况下，它工作效率很高
干杯！