⚙️AlgorithmAdvanced

Rectangle Union Area

Key Points

  • •
    The union area of many axis-aligned rectangles can be computed efficiently using a sweep line over x and a segment tree tracking covered y-length.
  • •
    We convert each rectangle into two events (enter at x1, leave at x2) and compress all distinct y-coordinates to index ranges.
  • •
    Between consecutive x-events, the covered y-length is constant; multiplying it by the x-gap and summing yields the total area.
  • •
    A segment tree stores for each y-interval whether it is covered by at least one rectangle and its total covered length.
  • •
    When a node’s cover counter is positive, its entire y-range contributes; otherwise, it sums its children’s contributions.
  • •
    Coordinate compression ensures O(n) y-intervals, turning updates into O(log n) each and the full algorithm into O(n n).
  • •
    Use half-open intervals [y1, y2) to avoid double counting at shared edges and to match the segment tree’s range logic.
  • •
    Watch for large coordinates and potential overflow; prefer 128-bit accumulation for integer inputs or long double for real inputs.

Prerequisites

  • →Sorting and event processing — The sweep line requires understanding how to sort events and process equal-x groups correctly.
  • →Segment trees and range updates — Maintaining covered length efficiently relies on a segment tree supporting range add and pull operations.
  • →Coordinate compression — We map large coordinates to dense indices for feasible segment tree sizes and O(log n) updates.
  • →Big-O notation — Analyzing the time and space complexity clarifies why the algorithm is efficient.
  • →Numerical precision and integer overflow — Choosing between 64-bit, 128-bit, and floating-point affects correctness of the final area.

Detailed Explanation

Tap terms for definitions

01Overview

The rectangle union area problem asks: given many axis-aligned rectangles on a plane, what is the total area covered by at least one rectangle? Naively summing areas and subtracting overlaps is impractical because overlaps can occur in complex patterns involving multiple rectangles. A robust strategy is to observe that, as we move a vertical line (a sweep line) from left to right, the set of y-intervals covered at the current x changes only at rectangle boundaries. If we can maintain the total vertical length covered by rectangles at the current x, then the area gained while moving from x to the next event x' is simply covered_length_y × (x' − x). To maintain covered length quickly, we discretize (compress) all y-coordinates that appear as rectangle edges and build a segment tree on the resulting elementary y-intervals. Each rectangle contributes two events: add its [y1, y2) coverage at x1 and remove it at x2. Handling these events in sorted order of x, and updating the segment tree for each add/remove, lets us accumulate the area in near-linear time. This approach is standard in computational geometry contests because it carefully avoids double counting, scales to large inputs, and provides deterministic precision when coordinates are integers.

02Intuition & Analogies

Imagine projecting all rectangles onto a tall vertical ruler placed at position x. The parts of the ruler covered by any rectangle at that x add up to some length L(x). If you nudge the ruler slightly to the right, the covered parts barely change—except when you cross a rectangle’s left or right edge. Thus, between such edges, L(x) is constant. The total area is just the sum of rectangle strips you sweep over: area = (width of strip) × (covered vertical length in that strip). The catch is: at any moment, many rectangles may overlap; but we care only about the union, not how many times a point is covered. To track that union on the vertical ruler, divide the y-axis into small elementary segments based on all rectangle y-coordinates (like marking every unique top and bottom edge on the ruler). For each elementary segment, count how many rectangles currently cover it as the sweep progresses. If the count is zero, it contributes no length; if it’s positive, it contributes its full height once. A segment tree is a fast tool to store this per-segment coverage and to update whole ranges quickly when a new rectangle starts or ends. Think of the tree as a hierarchy of ruler sections: if an entire large section is known to be covered, you don’t need to examine its subparts. This is why updates and queries stay fast, even for tens of thousands of rectangles.

03Formal Definition

Let R = {([, ) [, ))}_{i=1}^{n} be a set of axis-aligned rectangles with and . Define the covered-length function L(x) = \operatorname{measure}\big(\{ y (x, y) \}\big). The union area is A = L(x)\,dx. Because L(x) changes only at x in E = \{, \}, sort E = x^{(1)} < < < . For x [, ), L(x) is constant; denote it by . Then A = \,\big( - x^{(j)}\big). To compute efficiently, collect all distinct y-coordinates Y = \{, \} sorted, which induces elementary intervals = [, ) for ,,-1. Maintain a cover count (x) for each at the current sweep position; then L(x) = ( - ). A segment tree over indices m supports range-add updates (increment/decrement over indices corresponding to [, )) and querying the total union length L(x) as the root’s maintained length: if a node’s cover , its length equals the geometric length of its y-interval; otherwise, it equals the sum of its children’s lengths.

04When to Use

Use this technique when you need the exact area of a union of many axis-aligned rectangles and the input size is large (n up to 2e5 is common in contests). It is ideal when rectangles may heavily overlap, making inclusion–exclusion or grid-based counting infeasible. The method generalizes to counting union length of intervals in 1D (a warm-up), and with care, to computing measures in higher dimensions using more complex structures. Apply it in layout engines (computing visible area), VLSI design (area coverage), GIS (union of parcels), image processing (bounding box unions), and competitive programming problems asking for union area, often with large coordinates requiring 64-bit or 128-bit integers. Prefer this over naive plane subdivision or polygon union when rectangles are axis-aligned because the segment tree exploits this structure to avoid expensive geometric operations. If coordinates are floating-point, it still works well by compressing distinct y-values and using long double, provided numerical tolerances are respected.

⚠️Common Mistakes

Common pitfalls include: (1) Not using half-open intervals [y1, y2), which can double-count shared edges; half-open semantics ensure adjacent rectangles don’t create artificial overlap. (2) Forgetting to compress y and trying to build a tree over raw coordinates—this explodes memory/time when coordinates are large. (3) Mixing up segment indices: remember there are |Y|−1 elementary y-intervals between |Y| coordinate values; updates should target intervals, not points. (4) Overflow: accumulating area in 64-bit may overflow when coordinates are up to 1e9 and n is large; prefer __int128 for integer inputs or long double for real inputs. (5) Incorrect event ordering: accumulate area using the previous covered length times (x_cur − x_prev) before applying events at x_cur; then apply all events with the same x together. (6) Mishandling degenerate rectangles with zero width/height; they should be skipped. (7) Off-by-one errors in mapping y to indices and in the segment tree’s [l, r) convention. (8) Not initializing or recomputing node lengths correctly when cover count returns to zero—ensure the node pulls from children in that case.

Key Formulas

Area as integral of covered length

Explanation: The union area equals the integral over x of the vertical length covered at that x. This continuous view motivates sweeping: between events, L(x) is constant.

Discrete sweep sum

Explanation: Since changes occur only at event x-values, the area is a sum over strips. Multiply the covered y-length in each strip by its width and sum.

Covered length from cover counts

Explanation: The vertical union length equals the sum of elementary segment lengths whose cover count is positive. The Iverson bracket [] is 1 if the condition holds and 0 otherwise.

Segment tree node invariant

Explanation: A node’s covered length equals its full geometric length if its cover counter is positive; otherwise, it is the sum of its children’s covered lengths. This maintains union length at the root.

Compressed y bound

Explanation: The number of distinct y-coordinates M is at most twice the number of rectangles because each rectangle contributes up to two y-edges. Hence there are at most M−1 elementary y-intervals.

Time complexity

Explanation: We sort O(n) events, and process each event with an O( n) segment tree update. Building and memory operations are linear in the number of compressed coordinates.

Space complexity

Explanation: We store O(n) events, O(n) compressed coordinates, and a segment tree of size proportional to the number of y-intervals.

Complexity Analysis

Let n be the number of rectangles and M the number of distinct y-coordinates after compression. Each rectangle yields two events (enter and exit), so there are O(n) events. Sorting these events by x takes O(n log n). The segment tree is built over the elementary y-intervals defined by the M distinct coordinates, hence it has O(M) nodes; since each rectangle contributes at most two y-values, and the tree’s size is O(n). For each event, we perform a range add on [y1_idx, y2_idx) which costs O(log M) time because we recurse over at most one path per level. After each event group at the same x, we read the root’s covered length in O(1) and multiply by the x-gap to accumulate into the area. Thus, the total time is O(n log n) from sorting plus O(n log n) from updates, resulting in T(n) = O(n log n). Space usage is O(n) to store events, the compressed y-array, and the segment tree arrays (cover counters and lengths). If coordinates are integers up to 10^9 and n up to 2·10^5, the area may exceed 64-bit; use 128-bit accumulation to avoid overflow. With floating-point coordinates, use long double to reduce rounding error. The algorithm is memory-friendly because it avoids storing pairwise intersections or planar subdivisions, which can be quadratic in the worst case.

Code Examples

Rectangle Union Area (Integer coordinates, __int128-safe)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Compute the union area of axis-aligned rectangles with integer coordinates.
5// Uses sweep line over x and a segment tree over compressed y-intervals.
6// Accumulates area in __int128 to avoid overflow.
7
8struct Event {
9    long long x;   // sweep position
10    int y1, y2;    // indices in compressed Y for [y1, y2)
11    int typ;       // +1 for add, -1 for remove
12    bool operator<(const Event& other) const {
13        return x < other.x;
14    }
15};
16
17struct SegTree {
18    int n; // number of elementary segments = Y.size()-1
19    vector<int> cover;         // cover count per node
20    vector<long long> length;  // covered length per node (geometric length)
21    const vector<long long>& Y; // reference to compressed coordinates
22
23    SegTree(int n_, const vector<long long>& Y_) : n(n_), cover(4*n_, 0), length(4*n_, 0), Y(Y_) {}
24
25    // Update cover counts on interval [ql, qr) with value val (val in {+1, -1})
26    void update(int idx, int l, int r, int ql, int qr, int val) {
27        if (qr <= l || r <= ql) return; // no overlap
28        if (ql <= l && r <= qr) {
29            cover[idx] += val;
30            pull(idx, l, r);
31            return;
32        }
33        int mid = (l + r) >> 1;
34        update(idx<<1, l, mid, ql, qr, val);
35        update(idx<<1|1, mid, r, ql, qr, val);
36        pull(idx, l, r);
37    }
38
39    void pull(int idx, int l, int r) {
40        if (cover[idx] > 0) {
41            // Entire segment [l, r) is covered
42            length[idx] = Y[r] - Y[l];
43        } else {
44            if (l + 1 == r) {
45                // Leaf segment not covered
46                length[idx] = 0;
47            } else {
48                length[idx] = length[idx<<1] + length[idx<<1|1];
49            }
50        }
51    }
52
53    long long covered_length() const {
54        return length[1];
55    }
56};
57
58// Helper to print __int128
59string to_string_int128(__int128 v) {
60    if (v == 0) return "0";
61    bool neg = v < 0;
62    if (neg) v = -v;
63    string s;
64    while (v > 0) {
65        int digit = (int)(v % 10);
66        s.push_back('0' + digit);
67        v /= 10;
68    }
69    if (neg) s.push_back('-');
70    reverse(s.begin(), s.end());
71    return s;
72}
73
74int main() {
75    ios::sync_with_stdio(false);
76    cin.tie(nullptr);
77
78    int n;
79    if (!(cin >> n)) return 0;
80    struct Rect { long long x1,y1,x2,y2; };
81    vector<Rect> rects;
82    rects.reserve(n);
83
84    vector<long long> Ys;
85    Ys.reserve(2*n);
86
87    for (int i = 0; i < n; ++i) {
88        long long x1,y1,x2,y2;
89        cin >> x1 >> y1 >> x2 >> y2;
90        if (x1 > x2) swap(x1, x2);
91        if (y1 > y2) swap(y1, y2);
92        if (x1 == x2 || y1 == y2) continue; // degenerate, skip
93        rects.push_back({x1,y1,x2,y2});
94        Ys.push_back(y1);
95        Ys.push_back(y2);
96    }
97
98    if (rects.empty()) {
99        cout << 0 << '\n';
100        return 0;
101    }
102
103    // Coordinate compression of Y
104    sort(Ys.begin(), Ys.end());
105    Ys.erase(unique(Ys.begin(), Ys.end()), Ys.end());
106
107    // Build events
108    vector<Event> evs;
109    evs.reserve(2*rects.size());
110    auto get_idx = [&](long long y) {
111        return (int)(lower_bound(Ys.begin(), Ys.end(), y) - Ys.begin());
112    };
113    for (auto &r : rects) {
114        int y1 = get_idx(r.y1);
115        int y2 = get_idx(r.y2);
116        evs.push_back({r.x1, y1, y2, +1});
117        evs.push_back({r.x2, y1, y2, -1});
118    }
119    sort(evs.begin(), evs.end());
120
121    // Segment tree built over elementary segments [Ys[i], Ys[i+1]) for i in [0..m-2]
122    // So nSegments = Ys.size()-1; if nSegments == 0 => no area
123    int m = (int)Ys.size();
124    if (m < 2) { cout << 0 << '\n'; return 0; }
125    SegTree st(m-1, Ys);
126
127    __int128 area = 0;
128    long long prev_x = evs.front().x;
129
130    // Process events grouped by x
131    size_t i = 0, E = evs.size();
132    while (i < E) {
133        long long x = evs[i].x;
134        // Accumulate area for [prev_x, x)
135        long long dx = x - prev_x;
136        if (dx != 0) {
137            area += (__int128)st.covered_length() * dx;
138            prev_x = x;
139        }
140        // Apply all events at x
141        while (i < E && evs[i].x == x) {
142            st.update(1, 0, m-1, evs[i].y1, evs[i].y2, evs[i].typ);
143            ++i;
144        }
145    }
146
147    cout << to_string_int128(area) << '\n';
148    return 0;
149}
150

This program reads rectangles, filters degenerates, compresses y-coordinates, converts each rectangle into two events, and sweeps over sorted x. A segment tree over elementary y-intervals maintains the currently covered vertical length. For each gap in x, we add covered_length × dx to the total area. We use __int128 to safely accumulate large areas.

Time: O(n log n)Space: O(n)
Rectangle Union Area with Floating-Point Coordinates (long double)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Computes union area for rectangles with floating-point coordinates.
5// Uses long double to reduce rounding error. Coordinate compression still applies.
6
7struct Event {
8    long double x;
9    int y1, y2;
10    int typ;
11    bool operator<(const Event& other) const { return x < other.x; }
12};
13
14struct SegTree {
15    int n;
16    vector<int> cover;
17    vector<long double> length;
18    const vector<long double>& Y;
19    SegTree(int n_, const vector<long double>& Y_) : n(n_), cover(4*n_, 0), length(4*n_, 0), Y(Y_) {}
20    void update(int idx, int l, int r, int ql, int qr, int val) {
21        if (qr <= l || r <= ql) return;
22        if (ql <= l && r <= qr) { cover[idx] += val; pull(idx, l, r); return; }
23        int mid = (l + r) >> 1;
24        update(idx<<1, l, mid, ql, qr, val);
25        update(idx<<1|1, mid, r, ql, qr, val);
26        pull(idx, l, r);
27    }
28    void pull(int idx, int l, int r) {
29        if (cover[idx] > 0) length[idx] = Y[r] - Y[l];
30        else length[idx] = (l+1==r) ? 0.0L : length[idx<<1] + length[idx<<1|1];
31    }
32    long double covered_length() const { return length[1]; }
33};
34
35int main(){
36    ios::sync_with_stdio(false);
37    cin.tie(nullptr);
38
39    int n; if(!(cin>>n)) return 0;
40    struct Rect{ long double x1,y1,x2,y2; };
41    vector<Rect> rects; rects.reserve(n);
42    vector<long double> Ys; Ys.reserve(2*n);
43
44    for(int i=0;i<n;++i){
45        long double x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
46        if (x1 > x2) swap(x1,x2);
47        if (y1 > y2) swap(y1,y2);
48        if (fabsl(x1 - x2) < 1e-18L || fabsl(y1 - y2) < 1e-18L) continue;
49        rects.push_back({x1,y1,x2,y2});
50        Ys.push_back(y1); Ys.push_back(y2);
51    }
52
53    if(rects.empty()){ cout<<fixed<<setprecision(10)<<0.0L<<"\n"; return 0; }
54
55    sort(Ys.begin(), Ys.end()); Ys.erase(unique(Ys.begin(), Ys.end(), [](long double a, long double b){ return fabsl(a-b) < 1e-18L; }), Ys.end());
56
57    auto get_idx = [&](long double y){ return (int)(lower_bound(Ys.begin(), Ys.end(), y, [](long double a, long double b){ return a < b - 1e-18L; }) - Ys.begin()); };
58
59    vector<Event> evs; evs.reserve(2*rects.size());
60    for(auto &r: rects){
61        int y1 = get_idx(r.y1); int y2 = get_idx(r.y2);
62        evs.push_back({r.x1, y1, y2, +1});
63        evs.push_back({r.x2, y1, y2, -1});
64    }
65    sort(evs.begin(), evs.end());
66
67    int m = (int)Ys.size();
68    if(m < 2){ cout<<fixed<<setprecision(10)<<0.0L<<"\n"; return 0; }
69    SegTree st(m-1, Ys);
70
71    long double area = 0.0L;
72    long double prev_x = evs.front().x;
73
74    size_t i=0,E=evs.size();
75    while(i<E){
76        long double x = evs[i].x;
77        long double dx = x - prev_x;
78        if (fabsl(dx) > 1e-18L) {
79            area += st.covered_length() * dx;
80            prev_x = x;
81        }
82        while(i<E && fabsl(evs[i].x - x) < 1e-18L){
83            st.update(1, 0, m-1, evs[i].y1, evs[i].y2, evs[i].typ);
84            ++i;
85        }
86    }
87
88    cout<<fixed<<setprecision(10)<<area<<"\n";
89    return 0;
90}
91

This variant handles floating-point inputs by compressing long double y-values and comparing with a small epsilon to mitigate rounding issues. The logic mirrors the integer version, but all lengths and the area are long double.

Time: O(n log n)Space: O(n)
Warm-up: 1D Union Length of Intervals via Segment Tree
1#include <bits/stdc++.h>
2using namespace std;
3
4// Given intervals [l_i, r_i) on a line, compute the total union length.
5// This is the 1D analog of the y-length subproblem used in rectangle area.
6
7struct SegTree {
8    int n;
9    vector<int> cover;
10    vector<long long> length;
11    const vector<long long>& X; // compressed coordinates
12    SegTree(int n_, const vector<long long>& X_) : n(n_), cover(4*n_, 0), length(4*n_, 0), X(X_) {}
13    void update(int idx, int l, int r, int ql, int qr, int val) {
14        if (qr <= l || r <= ql) return;
15        if (ql <= l && r <= qr) { cover[idx] += val; pull(idx, l, r); return; }
16        int mid = (l + r) >> 1;
17        update(idx<<1, l, mid, ql, qr, val);
18        update(idx<<1|1, mid, r, ql, qr, val);
19        pull(idx, l, r);
20    }
21    void pull(int idx, int l, int r) {
22        if (cover[idx] > 0) length[idx] = X[r] - X[l];
23        else length[idx] = (l+1==r) ? 0 : length[idx<<1] + length[idx<<1|1];
24    }
25    long long covered_length() const { return length[1]; }
26};
27
28int main(){
29    ios::sync_with_stdio(false);
30    cin.tie(nullptr);
31
32    int n; if(!(cin>>n)) return 0;
33    vector<pair<long long,long long>> segs;
34    segs.reserve(n);
35    vector<long long> X; X.reserve(2*n);
36
37    for(int i=0;i<n;++i){
38        long long l,r; cin>>l>>r; if(l>r) swap(l,r); if(l==r) continue;
39        segs.push_back({l,r});
40        X.push_back(l); X.push_back(r);
41    }
42    if(segs.empty()){ cout<<0<<"\n"; return 0; }
43
44    sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
45    auto idx = [&](long long x){ return (int)(lower_bound(X.begin(), X.end(), x) - X.begin()); };
46
47    SegTree st((int)X.size()-1, X);
48    for(auto [l,r]: segs){ st.update(1, 0, (int)X.size()-1, idx(l), idx(r), +1); }
49
50    cout << st.covered_length() << "\n";
51    return 0;
52}
53

This program solves the 1D union-length problem using the same cover-count and pull logic as in the rectangle algorithm. It demonstrates how coordinate compression and a segment tree compute a union measure without double counting.

Time: O(n log n)Space: O(n)