题目描述

二维平面上有 N 条直线，形式为 y = kx + b，其中 k、b 为整数且 k > 0。所有直线以 [k, b] 的形式存于二维数组 lines 中，不存在重合的两条直线。两两直线之间可能存在一个交点，最多会有 $C_N^2$ 个交点。我们用一个平行于坐标轴的矩形覆盖所有的交点，请问这个矩形最小面积是多少。若直线之间无交点、仅有一个交点或所有交点均在同一条平行坐标轴的直线上，则返回 0。

注意：返回结果是浮点数，与标准答案 绝对误差或相对误差 在 10^-4 以内的结果都被视为正确结果。

样例

输入：lines = [[2,3],[3,0],[4,1]]
输出：48.00000
解释：三条直线的三个交点为 (3, 9) (1, 5) 和 (-1, -3)。
最小覆盖矩形左下角为 (-1, -3) 右上角为 (3, 9)，面积为 48。

输入：lines = [[1,1],[2,3]]
输出：0.00000
解释：仅有一个交点 (-2，-1)

限制

• 1 <= lines.length <= 10^5 且 lines[i].length == 2
• 1 <= lines[0] <= 10000
• -10000 <= lines[1] <= 10000
• 与标准答案绝对误差或相对误差在 10^-4 以内的结果都被视为正确结果。

算法

(数学，贪心) $O(n \log n)$

1. 矩形的最小面积等于所有交点中，横坐标的最大值减去最小值，与纵坐标的最大值减去最小值的乘积。
2. 先看横坐标的最大值与最小值。联立第 $i$ 条与第 $j$ 条直线，假设两个直线的斜率不相等，则交点的横坐标表达式为 $x = -\frac{b_i - b_j}{k_i - k_j}$。
3. 如果把两条直线 $(k_i, b_i)$ 和 $(k_j, b_j)$ 看做两个点的话，这两个点之间斜率的相反数就是交点的横坐标。则问题可以转化为，找到所有直线代表的点中，斜率最大和最小的两对点。
4. 这个问题可以通过贪心排序解决，假设需要求最大的横坐标，则将所有直线（点）按照 $k$ 从小到大排序，$k$ 值相同的，按照 $b$ 从小到大排序。在 $k_i \neq k_j$ 时，计算负斜率 $-\frac{b_i - b_j}{k_i - k_j}$，然后更新最大的横坐标值。
5. 这是因为，最小或最大的斜率总是诞生于相邻两个 $k$ 值之间。假设 $k_i < k_j$，则找到 $k_i$ 中最大的 $b$ 值减去 $k_j$ 中最小的 $b$ 值，然后除以 $k_i - k_j$ 就是最小的斜率，取相反数就是最大的横坐标。
6. 同理，找到 $k_i$ 中最小的 $b$ 值减去 $k_j$ 中最大的 $b$ 值，然后除以 $k_i - k_j$ 就是最大的斜率，取相反数就是最小的横坐标。可以在纸上画一下就可以看出贪心的结果，这里不再使用严谨的数学进行证明。
7. 对于纵坐标，将直线方程进行变换，即 $y = kx + b$ 变为 $x = \frac{1}{k}y - \frac{b}{k}$，然后套用横坐标的方法求解。这里需要注意 $k = 0$ 的情况，如果有这种情况，将 $k = 0$ 的直线单独拿出来，找到其 $b$ 值的最大最小值分别更新最大最小的总坐标。

时间复杂度

• 排序常数次所有直线，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储临时数组。

C++ 代码

class Solution {
private:
    bool has_intersection(vector<vector<int>> &lines) {
        sort(lines.begin(), lines.end());
        const int n = lines.size();
        for (int i = 1; i < n; i++)
            if (lines[i][0] != lines[i - 1][0])
                return true;

        return false;
    }

    double get_min_x(vector<vector<int>> &lines) {
        sort(lines.begin(), lines.end(), [](const vector<int> &p, const vector<int> &q) {
            if (p[0] != q[0])
                return p[0] < q[0];
            return p[1] > q[1];
        });

        const int n = lines.size();
        double min_x = 1e100;

        for (int i = 1; i < n; i++) {
            int ki = lines[i][0], bi = lines[i][1];
            int kj = lines[i - 1][0], bj = lines[i - 1][1];
            if (ki != kj)
                min_x = min(min_x, 1.0 * (bj - bi) / (ki - kj));
        }

        return min_x;
    }

    double get_max_x(vector<vector<int>> &lines) {
        sort(lines.begin(), lines.end(), [](const vector<int> &p, const vector<int> &q) {
            if (p[0] != q[0])
                return p[0] < q[0];
            return p[1] < q[1];
        });

        const int n = lines.size();
        double max_x = -1e100;

        for (int i = 1; i < n; i++) {
            int ki = lines[i][0], bi = lines[i][1];
            int kj = lines[i - 1][0], bj = lines[i - 1][1];
            if (ki != kj)
                max_x = max(max_x, 1.0 * (bj - bi) / (ki - kj));
        }

        return max_x;
    }

    double get_min_y(vector<vector<int>> &lines) {
        vector<vector<int>> nz;
        double min_y = 1e100;

        for (const auto &l : lines)
            if (l[0] != 0) nz.push_back(l);
            else min_y = min(min_y, double(l[1]));

        sort(nz.begin(), nz.end(), [](const vector<int> &p, const vector<int> &q) {
            if (p[0] != q[0])
                return 1.0 / p[0] < 1.0 / q[0];

            return 1.0 * p[1] / p[0] < 1.0 * q[1] / q[0];
        });

        const int n = nz.size();

        for (int i = 1; i < n; i++) {
            int ki = nz[i][0], bi = nz[i][1];
            int kj = nz[i - 1][0], bj = nz[i - 1][1];
            if (ki != kj)
                min_y = min(min_y, 1.0 * (ki * bj - kj * bi) / (ki - kj));
        }

        return min_y;
    }

    double get_max_y(vector<vector<int>> &lines) {
        vector<vector<int>> nz;
        double max_y = -1e100;

        for (const auto &l : lines)
            if (l[0] != 0) nz.push_back(l);
            else max_y = max(max_y, double(l[1]));

        sort(nz.begin(), nz.end(), [](const vector<int> &p, const vector<int> &q) {
            if (p[0] != q[0])
                return 1.0 / p[0] < 1.0 / q[0];

            return 1.0 * p[1] / p[0] > 1.0 * q[1] / q[0];
        });

        const int n = nz.size();

        for (int i = 1; i < n; i++) {
            int ki = nz[i][0], bi = nz[i][1];
            int kj = nz[i - 1][0], bj = nz[i - 1][1];
            if (ki != kj)
                max_y = max(max_y, 1.0 * (ki * bj - kj * bi) / (ki - kj));
        }

        return max_y;
    }

public:
    double minRecSize(vector<vector<int>>& lines) {
        if (!has_intersection(lines))
            return 0;

        return (get_max_x(lines) - get_min_x(lines)) *
            (get_max_y(lines) - get_min_y(lines));
    }
};