Rectangle Union Area

The union area of axis-aligned rectangles counts every covered region once, regardless of overlap. Sweeping x turns this into covered y-length times slab width. A segment tree tracks that length under rectangle entries and exits. Its leaves represent intervals between compressed coordinates, not individual coordinate points; this distinction is the core of a correct implementation.

Prerequisites: Sweep Line Fundamentals; coordinate compression; Segment Tree.

Build the idea

1. Split rectangles into events

   Normalize each rectangle’s corner order and discard zero width or height because it contributes no area. At x1 add coverage over [y1,y2); at x2 remove it. Between consecutive event coordinates the active y-union is unchanged, so its length multiplied by the x-gap is exactly the union area of that slab.

2. Compress intervals, not lengths

   Sort all y-endpoints into ys. Leaf i represents the real interval [ys[i],ys[i+1]), whose length may be much larger than one. An update for endpoints at indices l,r covers leaf range [l,r). Coordinate compression preserves ordering, not distances: always compute geometric length using original ys values.

   $$\mathrm{area}+=\mathrm{coveredYLength}·(x-\mathrm{previousX})$$

3. Maintain cover and length

   cover[node] counts full-range updates stored at that node. If positive, its entire span is covered and length[node]=ys[r]−ys[l]. If zero at a leaf, length is zero. If zero at an internal node, sum child lengths. Child states are retained even while a parent is fully covered, so removing a large rectangle correctly reveals remaining smaller rectangles.

4. Group equal x and accumulate first

   Before changing coverage at x, add length[root]·(x−previous). Then apply every event at x and move previous. Events at the same coordinate have zero-width gaps, so their internal order cannot change area; grouping states the invariant cleanly. The balanced tree updates only O(log n) canonical nodes for each y-interval.

5. Trace the overlap

   Rectangles [0,2]×[0,2] and [1,3]×[1,3] each have area 4 but overlap in a unit square. The x-slabs have covered lengths 2 on [0,1), 3 on [1,2), and 2 on [2,3), giving 7. A simple sum would incorrectly produce 8. The tree root supplies those union lengths without enumerating individual y-cells.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Event{
    long long x,y1,y2;
    int delta;
};
struct SegmentTree{
    const std::vector<long long>&y;
    std::vector<int>cover;
    std::vector<long long>length;
    explicit SegmentTree(const std::vector<long long>&ys)
        :y(ys),cover(4*ys.size()),length(4*ys.size()){
    }
    void update(int node,int l,int r,int ql,int qr,int delta){
        if(qr<=l||r<=ql){
            return;
        }
        if(ql<=l&&r<=qr){
            cover[node]+=delta;
        }
        else{
            int m=(l+r)/2;
            update(node*2,l,m,ql,qr,delta);
            update(node*2+1,m,r,ql,qr,delta);
        }
        // Positive local coverage hides (but does not erase) child coverage.
        if(cover[node]>0){
            length[node]=y[r]-y[l];
        }
        else if(r-l==1){
            length[node]=0;
        }
        else{
            length[node]=length[node*2]+length[node*2+1];
        }
    }
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Event>events;
    std::vector<long long>ys;
    for(int i=0;i<n;++i){
        long long x1,y1,x2,y2;
        std::cin>>x1>>y1>>x2>>y2;
        if(x1>x2){
            std::swap(x1,x2);
        }
        if(y1>y2){
            std::swap(y1,y2);
        }
        if(x1==x2||y1==y2){
            continue;
        }
        events.push_back({x1,y1,y2,1});
        events.push_back({x2,y1,y2,-1});
        ys.push_back(y1);
        ys.push_back(y2);
    }
    if(events.empty()){
        std::cout<<0<<'\n';
        return 0;
    }
    std::sort(ys.begin(),ys.end());
    ys.erase(std::unique(ys.begin(),ys.end()),ys.end());
    std::sort(events.begin(),events.end(),[](Event a,Event b){
        return a.x<b.x;
    });
    SegmentTree tree(ys);
    long long area=0,previous=events[0].x;
    for(int i=0;i<(int)events.size();){
        long long x=events[i].x;
        area+=tree.length[1]*(x-previous);
        while(i<(int)events.size()&&events[i].x==x){
            Event e=events[i++];
            int l=std::lower_bound(ys.begin(),ys.end(),e.y1)-ys.begin(),
                r=std::lower_bound(ys.begin(),ys.end(),e.y2)-ys.begin();
            tree.update(1,0,ys.size()-1,l,r,e.delta);
        }
        previous=x;
    }
    std::cout<<area<<'\n';
}

Complexity analysis

O(n log n) time: sort/compress O(n) endpoints and process 2n range updates in O(log n) each. O(n) events, compression and segment-tree storage. Area is at most the 2·10^6 by 2·10^6 bounding square, so fits long long.

Example input and output

Read n (0..100000), then x1 y1 x2 y2 per rectangle, integer coordinates within ±10^6. Reversed corners are normalized; zero-area rectangles ignored. Print the exact union area.

Input

2
0 0 2 2
1 1 3 3

Output

7

The two area-4 squares overlap in area 1, so their union is 4+4−1=7.

Practical applications

Use for coverage, layout overlap and total occupied area. Perimeter of a union needs additional information about connected covered intervals and boundary changes; covered length alone is insufficient. Rasterizing cells is only suitable for small coordinate grids.

Check your understanding

What length does a leaf for compressed indices i,i+1 represent?

Put it into practice

Compare against a unit-cell set on small integer-coordinate rectangles.