class Solution {
public:
double minRecSize(vector<vector<int>>& lines) {
}
};
LCP 37. 最小矩形面积
二维平面上有 $N$ 条直线，形式为 y = kx + b，其中 k、b为整数 且 k > 0。所有直线以 [k,b] 的形式存于二维数组 lines 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 $C_N^2$ 个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间无交点、仅有一个交点或所有交点均在同一条平行坐标轴的直线上，则返回0。
注意：返回结果是浮点数，与标准答案 绝对误差或相对误差 在 10^-4 以内的结果都被视为正确结果
示例 1：
输入：
lines = [[2,3],[3,0],[4,1]]输出：
48.00000解释：三条直线的三个交点为 (3, 9) (1, 5) 和 (-1, -3)。最小覆盖矩形左下角为 (-1, -3) 右上角为 (3,9)，面积为 48
示例 2：
输入：
lines = [[1,1],[2,3]]输出：
0.00000解释：仅有一个交点 (-2，-1）
限制：
1 <= lines.length <= 10^5 且 lines[i].length == 21 <= lines[0] <= 10000-10000 <= lines[1] <= 10000与标准答案绝对误差或相对误差在 10^-4 以内的结果都被视为正确结果原站题解
python3 解法, 执行用时: 308 ms, 内存消耗: 43.9 MB, 提交时间: 2023-07-19 18:05:44
'''
数学推导用k，b表示交点的横纵坐标找规律，求解交点横纵坐标的最大最小值然后进行求解。
'''
class Solution:
def minRecSize(self, lines: List[List[int]]) -> float:
lines.sort()
count, i, top = [[0]*3 for i in range(10000)], 0, 0
count[0][0], count[0][1] = lines[0][0], 0
for i in range(1, len(lines)):
if lines[i][0] != lines[i-1][0]:
count[top][2] = i-1
top += 1
count[top][0] = lines[i][0]
count[top][1] = i
count[top][2] = len(lines) - 1
if top == 0:
return 0
max_x = (lines[count[0][2]][1] - lines[count[1][1]][1])/(count[1][0] - count[0][0])
min_x = (lines[count[0][1]][1] - lines[count[1][2]][1])/(count[1][0] - count[0][0])
for i in range(1, top):
max_x = max(max_x, (lines[count[i][2]][1] - lines[count[i+1][1]][1])/(count[i+1][0] - count[i][0]))
min_x = min(min_x, (lines[count[i][1]][1] - lines[count[i+1][2]][1])/(count[i+1][0] - count[i][0]))
max_y = (lines[count[0][2]][1]* count[1][0] - lines[count[1][1]][1]* count[0][0])/(count[1][0] - count[0][0])
min_y = (lines[count[0][1]][1]* count[1][0] - lines[count[1][2]][1]* count[0][0])/(count[1][0] - count[0][0])
for i in range(1,top):
max_y = max(max_y, (lines[count[i][2]][1]* count[i+1][0] - lines[count[i+1][1]][1]* count[i][0])/(count[i+1][0] - count[i][0]))
min_y = min(min_y, (lines[count[i][1]][1]* count[i+1][0] - lines[count[i+1][2]][1]* count[i][0])/(count[i+1][0] - count[i][0]))
return (max_x - min_x) * (max_y - min_y)
python3 解法, 执行用时: 156 ms, 内存消耗: 44.5 MB, 提交时间: 2023-07-19 18:04:38
'''
考虑左下方无限远处，这时再往远走，所有直线之间的距离会越来越远，不会再有交点。
而慢慢靠近原点，最先出现交点的必是相邻两条直线。
'''
from collections import defaultdict
class Solution:
def minRecSize(self, lines: List[List[int]]) -> float:
d=defaultdict(list)
for line in lines:
d[line[0]].append(line[1])
xs,ys=[],[]
def intersect(f,g):
xs.append(x:=(g[1]-f[1])/(f[0]-g[0]))
ys.append(y:=f[0]*x+f[1])
k=sorted(d.keys())
for i,j in zip(k[:-1],k[1:]) :
intersect((i,min(d[i])),(j,max(d[j])))
intersect((i,max(d[i])),(j,min(d[j])))
return (max(xs)-min(xs))*(max(ys)-min(ys)) if xs else 0
cpp 解法, 执行用时: 284 ms, 内存消耗: 66.2 MB, 提交时间: 2023-07-19 18:02:03
/**
* 按(k, b)分类排序后，只有相邻两列的最上、最下两个顶点之间的连线才有可能构成答案
*
**/
class Solution {
public:
double minRecSize(vector<vector<int>>& f) {
int n = f.size();
vector<int> k(n, 0), b(n, 0);
sort(f.begin(), f.end());
for (int i = 0; i < n; i++) {
k[i] = f[i][0]; b[i] = f[i][1];
}
int p = 0, q = 0;
while (q < n && k[q] == k[p]) q++;
if (q >= n) return 0.;
double x_min = 1e100, x_max = -1e100;
double y_min = 1e100, y_max = -1e100;
for (; q < n;) {
int r = q;
while (r + 1 < n && k[r + 1] == k[q]) r++;
// [p, q - 1], [q, r]
double cx1 = 1.0 * (b[r] - b[p]) / (k[r] - k[p]);
double cx2 = 1.0 * (b[q] - b[q - 1]) / (k[q] - k[q - 1]);
x_min = min(x_min, min(cx1, cx2));
x_max = max(x_max, max(cx1, cx2));
double cy1 = 1.0 * (b[r] * k[p] - b[p] * k[r]) / (k[r] - k[p]);
double cy2 = 1.0 * (b[q] * k[q - 1] - b[q - 1] * k[q]) / (k[q] - k[q - 1]);
y_min = min(y_min, min(cy1, cy2));
y_max = max(y_max, max(cy1, cy2));
p = q;
while (q < n && k[q] == k[p]) q++;
}
return (x_max - x_min) * (y_max - y_min);
}
};