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
subject
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
Restrictions:
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
Sample
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 * r.dot(*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 {
public:
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_)
mapping[l[0]].insert(l[1]);
// 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
lines.push_back({});
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);
}
++it;
}
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))
points.push_back(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;
}
};