Force buckle LCP37 - Minimum rectangular area

Note: Question 5 of 2021 force buckle cup spring team competition

Key points of algorithm:

  • Intersection of two lines
  • Divide barrels by slope
  • Detail processing


Title Link

Title Description

There are NN straight lines on the two-dimensional plane in the form of y = kx + b, where K and B are integers and k > 0. All lines are stored in the two-dimensional array lines in the form of [k,b], and there are no coincident two lines. There may be an intersection between two lines, up to ( N 2 ) \binom{N}{2} (2N) intersections. We use a rectangle parallel to the coordinate axis to cover all intersections. What is the minimum area of this rectangle. If there is no intersection between lines, there is only one intersection, or all intersections are on a line with the same parallel coordinate axis, 0 is returned.

Note: the returned result is a floating-point number, and the result with absolute error or relative error within 1e-4 from the standard answer is regarded as the correct result


1 <= lines.length <= 10^5 And lines[i].length == 2
1 <= lines[0] <= 10000
-10000 <= lines[1] <= 10000
 The absolute error or relative error with the standard answer is within 10^-4 Results within are considered correct


Example 1:
Input: lines = [[2,3],[3,0],[4,1]]
Output: 48.00000
Explanation: the three intersections of three straight lines are (3, 9) (1, 5) and (- 1, - 3). The minimum coverage rectangle is (- 1, - 3) in the lower left corner and (3,9) in the upper right corner, with an area of 48

Example 2:
Input: lines = [[1,1],[2,3]]
Output: 0.00000
Explanation: there is only one intersection (- 2, - 1)

Problem solution

$1 algorithm

Give n straight lines, find all the intersections of these n straight lines, and then count the answers, that is, the maximum and minimum abscissa and ordinate of these points.

Because the order of magnitude of the intersection is O ( n 2 ) O(n^{2}) O(n2), so you can't handle all intersections completely.

Therefore, we should try our best to eliminate the points that certainly have no impact on the results, leave the points that may have an impact on the results, and then count the answers.

$1-1 algorithm for excluding points that have no effect on the result

$1-1-1 consider the case where no two straight lines are parallel

Sort the straight lines according to the slope, arrange them into a ring, and set the straight line as L 1 , L 2 , . . . , L n L_{1}, L_{2}, ..., L_{n} L1​,L2​,..., Ln​. Then there are only adjacent lines L i , L i + 1 L_{i}, L_{i+1} Li, Li+1 (including L n L_{n} Ln # and L 1 L_{1} The intersection of L1) has an impact on the result, and such intersections share O ( n ) O(n) O(n), and then count the answers. Therefore, the total complexity is O ( n ) O(n) O(n). Prove as follows

First, only the points on the convex hull are the points that affect the answer. For example, the midpoint a, B and C in the figure below are the three points on the convex hull.

Then consider each line segment constituting the convex hull. There are only two cases for these line segments: (1) this line segment belongs to one of the original lines (such as BC in the above figure), (2) this line segment does not belong to any original line (such as AB in the above figure). All intersections are on the same side of this line segment, or just on this line segment.

  • (1) For an original straight line (marked as Φ \Phi Φ) Convex hull line segment (marked as *): because all intersections are in a straight line Φ \Phi Φ On the same side or on the line segment *, so all lines are on the same side Φ \Phi Φ The other side of the is in a divergent shape, as shown in the figure below. Therefore, the two endpoints A and b of the convex hull segment * must be the line Φ \Phi Φ And slope and the straight line Φ \Phi Φ The intersection of the two closest lines, otherwise Φ \Phi Φ Another intersection will appear on the other side of the line, and the line segment * is not a convex hull line segment.

  • (2) For convex hull line segment (marked as *) that does not belong to any original line: the two endpoints A and b of line segment * must be the intersection of some two lines, and the two lines must also be adjacent to each other. Otherwise, if the slope of a straight line is between the two, there must be an intersection on the other side, * is not a convex hull segment. As shown in the figure below, a is the intersection of two adjacent slope lines, and b is the intersection of two adjacent slope lines (although there are three, the more one can be ignored)

$1-1-2 with parallel lines

For a set of parallel lines, only the two outermost lines need to be considered. In the algorithm without parallel lines, a line can be changed into two lines at most, so the original intersection to be considered can be changed into four at most, and the number of points is still O ( n ) O(n) O(n).

To sum up, the complete algorithm is as follows:

1. Divide all straight lines into buckets according to the slope, and keep the two with the largest and smallest intercept in each bucket
2. Enumerate each pair of buckets with adjacent slopes and find the intersection of each pair of straight lines in the two buckets
3. Traverse the statistical answers to these intersections

$1-2 algorithm for finding the intersection of line pairs

Given two straight lines, find the intersection. If the intersection does not exist, return false. The algorithm is as follows:

First write a straight line in two directions a ⃗ + p ⋅ b ⃗ \vec{a} + p \cdot \vec{b} a +p⋅b and c ⃗ + q ⋅ d ⃗ \vec{c} + q \cdot \vec{d} c +q⋅d , solving the equation a ⃗ + p ⋅ b ⃗ = c ⃗ + q ⋅ d ⃗ \vec{a} + p \cdot \vec{b} = \vec{c} + q \cdot \vec{d} a +p⋅b =c +q⋅d , after finding p, you can find the intersection of two lines.

p = ( c ⃗ − a ⃗ ) × d ⃗ b ⃗ × d ⃗ p = \frac{(\vec{c} - \vec{a}) \times \vec{d}}{\vec{b} \times \vec{d}} p=b ×d (c −a )×d ​

Note the case where the denominator is zero: two direction vectors b ⃗ \vec{b} b and d ⃗ \vec{d} d In parallel, false is returned in this case.

In order to save time during the competition, the template is directly used. The straight Line in the template is in the form of point plus direction Vector (directed straight Line). The template code is as follows (Line and Vector are also templates):

// Line intersects line
bool line_intersection(const Line& l1, const Line& l2, Vector2& x)
    double det = l1.b.cross(l2.b); // Two directions of the outer product of vectors
    // Parallel or overlapping returns false
    if(fabs(det) < EPS)
        return false;
    // Intersection of two directed lines
    Vector2 u = l1.a - l2.a;
    double t = l2.b.cross(u) / det;
    x = l1.a + l1.b * t;
    return true;

Line is the template of directed line (in the form of point plus direction vector): a ⃗ + p ⋅ b ⃗ \vec{a} + p \cdot \vec{b} a +p⋅b . The template code is as follows:

struct Line
    // line: a+pb, a is the point and b is the direction vector
    Vector2 a;
    Vector2 b;
    double deg; // Polar angle
    Line(Vector2 a, Vector2 b):a(a),b(b)
        deg = b.polar();
    bool operator<(const Line& l) const
        // Polar order of direction vector
        return deg < l.deg;

Vector2 is the template of two-dimensional vector, which realizes the common operations of vector addition and subtraction, number multiplication, inner product, outer product, normalization, polar angle and so on. The point and direction vectors are defined as two-dimensional vectors, and the codes are as follows:

// Template of two-dimensional vector
struct Vector2
    double x, y;
    explicit Vector2(double x_=0, double y_=0):x(x_),y(y_){}

    // Compare two vectors
    bool operator==(const Vector2& vec) const
        return fabs(x - vec.x) < EPS && fabs(y - vec.y) < EPS;
    bool operator<(const Vector2& vec) const
        if(fabs(x - vec.x) < EPS)
            return y < vec.y;
        return x < vec.x;

    // Addition and subtraction of vectors
    Vector2 operator+(const Vector2& vec) const
        return Vector2(x + vec.x, y + vec.y);
    Vector2 operator-(const Vector2& vec) const
        return Vector2(x - vec.x, y - vec.y);

    // Number multiplication of vectors
    Vector2 operator*(double a) const
        return Vector2(x * a, y * a);

    // Module of vector
    double norm() const
        return hypot(x, y);

    // Returns a unit vector in the same direction
    // Zero vector is not callable
    Vector2 normalize() const
        return Vector2(x / norm(), y / norm());

    // The angle from the positive direction of the x axis to the current vector
    double polar() const
        // atan2 returns (- PI, PI), corrected to [0, 2PI)
        // fmod find the remainder of the division of two real numbers
        return fmod(atan2(y, x) + 2 * PI, 2 * PI);

    // inner product
    double dot(const Vector2& vec) const
        return x * vec.x + y * vec.y;
    double cross(const Vector2& vec) const
        return x * vec.y - y * vec.x;

    // The result of mapping the current vector to another vector
    // The length of vec needs to be greater than 0
    Vector2 project(const Vector2& vec) const
        Vector2 r = vec.normalize();
        return r **this);

    // The angle between two vectors
    // Both vector lengths need to be greater than 0
    double insersection_angle(const Vector2& vec) const
        return acos(dot(vec) / norm() * vec.norm());

    // Judge whether two vectors are vertical
    // Both vector lengths need to be greater than 0
    bool perpendicular(const Vector2& vec) const
        return fabs(dot(vec)) < EPS;

    // Parallelogram area
    double parallelogram_area(const Vector2& vec) const
        return fabs(cross(vec));

    // Triangle area, you can find the polygon
    double triangle_area(const Vector2& vec) const
        return fabs(cross(vec)) / 2;

$2 code

const double PI = 2.0 * acos(0.0);
const double EPS = 1e-10;

// Template of two-dimensional vector
struct Vector2;

// Template of straight line in the form of point + direction vector
struct Line;

// Template for finding the intersection of two lines in the form of point + direction vector
bool line_intersection(const Line& l1, const Line& l2, Vector2& x);

class Solution {
    double minRecSize(vector<vector<int>>& lines_) {
        int n = lines_.size();
        if(n <= 2)
            return 0;
        // Divide buckets according to the slope, and maintain the ascending order with map. The intercept in the bucket is from small to large
        map<int, set<int>> mapping;
        for(const vector<int>& l: lines_)
        // Each slope takes the maximum and minimum intercept to construct line segments, and saves them in the vector according to the order in the map (that is, the order of slope from small to large)
        vector<vector<Line>> lines;
        auto it = mapping.begin();
        while(it != mapping.end())
            // A new slope is encountered and a new bucket with this slope needs to be allocated
            Vector2 b(1, it -> first); // Direction vector
            Vector2 a(0, *(it -> second).begin()); // Intercept point
            lines.back().emplace_back(a, b);
            if((it -> second).size() > 1)
                Vector2 b2(1, it -> first); // Direction vector
                Vector2 a2(0, *(it -> second).rbegin()); // Intercept point
                lines.back().emplace_back(a2, b2);
        if(lines.size() < 2) // All lines have only one slope and no intersection
            return 0;

        vector<Vector2> points; // The intersection formed by the straight lines of all adjacent slopes in the bucket
        for(int i = 0; i < (int)lines.size(); ++i)
            int j = (i + 1) % (int)lines.size();
            // lines[i] is one or two lines to be considered corresponding to the current slope
            // lines[j] is one or two lines to be considered corresponding to the next adjacent slope
            for(Line l1: lines[i])
                for(Line l2: lines[j])
                    Vector2 x(-1e9, -1e9);
                    if(line_intersection(l1, l2, x))

        // Statistical answer
        double min_x = points[0].x;
        double min_y = points[0].y;
        double max_x = points[0].x;
        double max_y = points[0].y;
        for(Vector2 p: points)
            min_x = min(min_x, p.x);
            min_y = min(min_y, p.y);
            max_x = max(max_x, p.x);
            max_y = max(max_y, p.y);
        if(abs(max_x - min_x) < EPS)
            return 0;
        if(abs(max_y - min_y) < EPS)
            return 0;
        double ans = abs(max_x - min_x) * abs(max_y - min_y);
        return ans;

Keywords: Algorithm leetcode

Added by mariolopes on Tue, 08 Mar 2022 21:23:05 +0200