Rectangular coverage area

Original link

The main idea of the topic ： In the standard rectangular coordinate system , Several rectangular The area is painted （ Be careful ： Rectangles may overlap ）. The rectangle is represented as $(x_1,y_1,x_2,y_2)$, Coordinates representing the two diagonal points of the rectangle . Find the total area covered by the paint .

keyword ： Line segment tree 、 Scanning line method
（ This problem is a very special application of line segment tree .）

$n$ A rectangle , Vertical edge $2n$ individual . Each vertical edge can use four parameters $(x,y_1,y_2,st)$ To describe , among $st$ Used to distinguish two sides in the same rectangle , It reflects the properties of the edge （ Into the side or Out of the way ）.

struct Segment
{
    
    int x, y1, y2;
    int st; // Reflect the nature of the line segment ：+1 It means "in" ,-1 Show the side 
    bool operator< (const Segment &s)const // The abscissa is used as the sorting standard 
    {
    
        return x < s.x;
    }
}seg[N * 2];

Read in $n$ A rectangle is actually read into this $2n$ Line segments ：

int n;
cin >> n;
for (int i = 0, t = 0; i < n; i ++)
{
    
	int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    seg[t ++] = {
    x1, y1, y2, +1}; seg[t ++] = {
    x2, y1, y2, -1};
}
sort(seg, seg + 2 * n); // According to the abscissa 2n Line segments are sorted 

The scanning line method is based on this $2n$ Based on line segments , Generate $2n$ Scan lines （ Possible overlap ）, On each straight line Length actually used namely The height of the rectangle , The distance between adjacent scan lines namely The length of the rectangle , Thus, the area of the rectangle between the two scan lines can be calculated . Add up all the areas , The final total area is obtained .

$$\begin{gathered} S_1=(seg[1].x-seg[0].x)\cdot h_1 \\ {S}_2=(seg[2].x-seg[1].x)\cdot h_2 \\ ⋮ \\ {S}_i=(seg[i].x-seg[i-1].x)\cdot h_i \end{gathered}$$$$S_{total}=S_1+S_2+\cdots +S_{2n-1}$$ for example ：

Convert to calculation ：

The advantage of this method is ： Just sweep from left to right , One step at a time . The information you need to know for each calculation is ：

1. Height of each new rectangle .
2. Width of each new rectangle .

The width of each new rectangle is very easy to calculate , Just sort the scanlines , The adjacent scan lines are subtracted to obtain .

The calculation of the height of each new rectangle is troublesome , because The length actually used on the scan line is affected by the previously enumerated scan lines .

The specific analysis is as follows ：

First of all, ask a question ：② How to calculate the height of rectangle No ？
The intuitive answer is ：$10+(25.5-20)=15.5$, Count it first ① No. rectangle height , Plus ② The extra part of rectangle No .
that ③ How to calculate the height of rectangle No ？
obviously ,$15.5-(15-10)=10.5$, First use ② Subtract the extra part from the high part of the rectangle .

that Why sometimes “ Come out more ” Is to add a value , occasionally “ Come out more ” Is to subtract a value ？
This problem is the core of the scan line method —— “ Into the side ” and “ Out of the way ” The problem of .

Define a rectangle , The height of the left side is “ Into the side ”, The height of the right side is “ Out of the way ”.

In fact, the so-called "from left to right" （ It can also be from top to bottom ）, Namely Scanning direction .

When sweeping from left to right , Encountered edge scan line , Then the edge entry interval is $+1$, Encountered edge scan line , For the boundary section $-1$, This is the law of adding or subtracting intervals .

This is actually a Difference Thought , Update the number of times each cell is covered , On the whole , All coverage times $\ge 1$ The cells of form the height of the current rectangle .

Specific implementation aspects , Enumerate scan lines according to the size of abscissa , To ensure that the latest actual length is used in the calculation , The whole section needs to be Dynamic maintenance , The common method is ： Line segment tree .

The whole interval is divided into 1 Divided by unit length , Each bottom node of the segment tree corresponds to an interval of unit length .

The specific storage structure is ：

struct Node
{
    
    int l, r; // The boundary unit interval of the interval corresponding to the node （ Be careful ： Not an endpoint , It is the unit interval at both ends ！）
    int cnt;  // The number of times that the interval corresponding to the node is covered （ Full coverage ）
    int len;  // The length of the interval covered by the node 
}tr[N * 4];

Thus the root node tr[1] It points to the entire interval ,tr[1].len It always reflects the effective length of the current interval .

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
struct Segment
{
    
    int x, y1, y2;
    int st; // Indicates the nature of the line segment ： Enter into  or  Out 
    bool operator< (const Segment &t)const // Sort by abscissa 
    {
    
        return x < t.x;
    }
}seg[N * 2];
struct
{
    
    int l, r; // The boundary of an interval 
    int cnt;  // The number of times the current interval is covered （ Full coverage ）
    int len;  // The length covered 
}tr[N * 4];

void build(int u, int l, int r)
{
    
    tr[u] = {
    l, r};

    if (l != r)
    {
    
        int mid = (l + r) / 2;
        build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);
    }
}

void pushup(int u)
{
    
    if (tr[u].cnt > 0) tr[u].len = tr[u].r - tr[u].l + 1;
    else 
    {
    
    	if (tr[u].l == tr[u].r) tr[u].len = 0;
    	else tr[u].len = tr[2 * u].len + tr[2 * u + 1].len;
    }
}
void modify(int u, int L, int R, int st)
{
    
    if (L <= tr[u].l && tr[u].r <= R)
    {
    
        tr[u].cnt += st;
        pushup(u);
    }
    else
    {
    
        int mid = (tr[u].l + tr[u].r) / 2;
        if (L <= mid) modify(2 * u, L, R, st);
        if (R > mid) modify(2 * u + 1, L, R, st);
        pushup(u);
    }
}

int main()
{
    
    build(1, 0, 9999); // Initializing line segment tree 

    int n;
    cin >> n;
    for (int i = 0, t = 0; i < n; i ++)
    {
    
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        seg[t ++] = {
    x1, y1, y2, +1}; seg[t ++] = {
    x2, y1, y2, -1};
    }
    sort(seg, seg + 2 * n); // Sort by abscissa 

    int res = 0;
    for (int i = 0; i < 2 * n; i ++)
    {
    
        if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x); // From 2 The line begins to count 
        modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].st); // Join in （ Or delete ） An interval （ according to k And decide ）
    }
    cout << res;

    return 0;
}