Algorithm {Find the area of the union of horizontal matrices}
Find the area of the union of horizontal matrices
Definition
In two-dimensional space, find the area of the union of several matrices (side lengths parallel to the X|Y axis);
Properties
Algorithm
Dynamic scan line (
O
(
N
?
l
o
g
N
)
O(N*logN)
O(N?logN))
Properties
Code
namespace ___Get_RectangleUnionArea_DynamicScanning{
#define LEF_( _i) std::get<0>(A[_i]) // The `X` coordinate on the left side of the i-th matrix;
#define RIG_( _i) std::get<2>(A[_i]) // The `X` coordinate on the right side of the i-th matrix;
#define LOW_( _i) std::get<1>(A[_i]) // The lower `Y` coordinate of the i-th matrix;
#define HIG_( _i) std::get<3>(A[_i]) // The `Y` coordinate of the i-th matrix;
using __PointType_ = remove_reference_t<decltype(LEF_(0))>; // Type of matrix vertex
___Hash_Sorting<Double> __HashY; // Discretize hashing of all `Y` coordinates
@TODO(Introduce the algorithm template `___DynamicIntervalCoverage` and modify it to the following code:
using __ValType_ = __PointType_ ;
__ValType_ __Get_ValSum( int _l, int _r){ // Get the sum of the interval `A[l] + ... + A[r]`;
return __HashY.Map.at(_r + 1) - __HashY.Map.at(_l);
}
);
__PointType_ Work( int _n){ // `n` matrices
__HashY.Initialize( 2*_n);
using ___SegmentType_ = tuple< __PointType_, __PointType_, __PointType_, bool>; // (X coordinate, Y coordinate (bottom), Y coordinate (top), mark (left/right)
vector< ___SegmentType_> ___Y_Segments( _n*2);
FOR_(i, 0, _n-1){
__HashY.Add( LOW_(i)); __HashY.Add( HIG_(i));
___Y_Segments[i<<1] = {LEF_(i), LOW_(i), HIG_(i), true};
___Y_Segments[i<<1|1] = {RIG_(i), LOW_(i), HIG_(i), false};
}
__HashY.Work();
sort( ___Y_Segments.begin(), ___Y_Segments.end(), []( auto & amp; _a, auto & amp; _b){
if( get<0>(_a) != get<0>(_b)){ return get<0>(_a) < get<0>(_b);} // `X coordinate` is incremented
return get<3>(_a) > get<3>(_b); // If the `X coordinates` are the same line segments, the *left* is in front and the right* is in the back, because *left* is adding *right* is eliminating the need Add first and then eliminate;
});
___DynamicIntervalCoverage::Initialize( __HashY.Map.size() - 1);
__PointType_ ANS = 0;
FOR_( i, 0, (int)___Y_Segments.size()-1){
__PointType_ curX = get<0>(___Y_Segments[i]);
int y_low = __HashY.Get_hash( get<1>(___Y_Segments[i]));
int y_hig = __HashY.Get_hash( get<2>(___Y_Segments[i]));
bool flag = get<3>(___Y_Segments[i]);
___DynamicIntervalCoverage::Modify( y_low, y_hig - 1, (flag ? 1 : -1)); // `[y_low...y_hig]`The *interval* corresponding to these points (that is, the points in the line segment tree) is `[ y_low...(y_hig-1)]`;
if( i<(int)___Y_Segments.size() & amp; & amp; Double_cmp(curX, get<0>(___Y_Segments[i + 1]))!=0){
ANS + = ___DynamicIntervalCoverage::Query().Sum * (get<0>(___Y_Segments[i + 1]) - curX);
}
}
return ANS;
}
#undef LEF_
#undef RIG_
#undef LOW_
#undef HIG_
} // ___Get_RectangleUnionArea_DynamicScanning
Examples
@LINK: https://www.acwing.com/problem/content/description/249/;
Scanline (
O
(
N
2
)
O(N^2)
O(N2))
Properties
Let SX be the removed sorted set of xl, xr (the X coordinates of the left and right sides) of all matrices, for example, it is [1, 5, 8], the first traversal of xl=1, xr=5 these two scan lines form a X: [xl,xr], Y : infinitearea
T
T
T (this area is infinite, it is a matrix without upper and lower edges), then a matrix (xll, yll)-(xrr,yrr) if it is related to the scan line area
T
T
T has (area
>
0
>0
>0 intersection) is equivalent to xll <= xl, xrr >= xr. At this time, the matrix is
T
T
The intersection of T is (xl,yll)-(xr,yrr) this matrix, because the intersection of any matrix and T is in the shape of (xl,?) -(xr,?) So we can only focus on ?, that is, compress the intersection (matrix) into a one-dimensional line segment [yll, yrr] , that is, given several [yl, yr] line segments and then perform the interval merging algorithm;
@DELI;
Use several x=? (lines parallel to the Y-axis) to divide the answer (ie, the union area) into several sub-areas Ai, that is, S = A1 + A2 + ..., and then find each Ai individually;
Code
{ // Scan lines to find the union area of horizontal matrices (O(N^2))
//<The time is `O(N^2)`;
#define LEF_( i) @TODO // The `X` coordinate on the left side of the i-th matrix;
#define RIG_( i) @TODO // The `X` coordinate on the right side of the i-th matrix;
#define LOW_( i) @TODO // The `Y` coordinate below the i-th matrix;
#define HIG_( i) @TODO // The `Y` coordinate of the i-th matrix;
using __PosType = decltype( LEF_(0)); // Type of coordinates
const int __N = @TODO; // Number of matrices
ASSERT_( __N > 0);
vector< __PosType> Xpos( __N*2); // All `LEF_(i)` are sorted from small to large;
for( int i = 0; i < __N; + + i){ Xpos[ i*2] = LEF_(i), Xpos[ i*2 + 1] = RIG_(i);}
sort(Xpos.begin(), Xpos.end());
vector< int> Ind( __N); // The matrix is sorted from small to large according to `LOW_()`;
iota(Ind.begin(), Ind.end(), 0);
sort( Ind.begin(), Ind.end(), [ & amp;]( int _a, int _b)->bool{ return LOW_(_a) < LOW_(_b);});
Double ANS = 0;
for( int i = 0; i + 1 < __N*2; + + i){
if(Xpos[i + 1] == Xpos[i]){ continue;}
auto l = Xpos[ i], r = Xpos[ i + 1]; // The two scan lines are `x=l, x=r`;
__PosType preLow = 1, preMaxHig = 0; // Template code for *interval merging*
for( int j = 0; j < __N; + + j){ // Traverse all matrices that have *intersection* with the current `x=l,x=r` scan line area
auto ind = Ind[j];
if( LEF_(ind) <= l & amp; & amp; RIG_(ind) >= r){
if( preLow > preMaxHig){ preLow = LOW_(ind), preMaxHig = HIG_(ind);}
else{
if( LOW_(ind) <= preMaxHig){ preMaxHig = max(preMaxHig, HIG_(ind));}
else{
ANS + = Double(r - l) * (preMaxHig - preLow);
preLow = LOW_(ind), preMaxHig = HIG_(ind);
}
}
}
}
if( preLow <= preMaxHig){
ANS + = Double(r - l) * (preMaxHig - preLow);
}
}
#undef LEF_
#undef RIG_
#undef LOW_
#undef HIG_
} // Find the union area of horizontal matrices (O(N^2))
Examples
Template @LINK: https://www.acwing.com/problem/content/3071/;