cppAcademy
FROM LEARNING TO COMPETING

Proficient.
Put your skills to the test.

Bulgarian Informatics Group B · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group B also includes challenging national-level problems. National-round tasks shared by Groups A and B are included. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP B2012 · MediumCoordinate compression

Rectangle Union Area

National Olympiad — Regional round (2012 season)

Submission name: rectarea.cpp

Solve in Editor →

Problem summary

Find the area covered by at least one of N axis-aligned rectangles. Rectangles may overlap, touch, or have zero area; their two input corners can appear in either order.

Input

N, followed by two opposite corners x1 y1 x2 y2 of each rectangle.

Output

The exact union area.

Constraints

1≤N≤100; integer coordinates have absolute value at most 10000.

Worked example

An independently prepared example for this explanation.

Input

2
1 1 3 3
2 2 4 4

Output

7

Solution analysis

  1. Collect and sort all distinct x-coordinates and y-coordinates of rectangle sides. They partition the plane into at most (2N−1)² elementary rectangular cells.
  2. Normalize each rectangle and mark every compressed cell inside it. Each cell is either fully covered or completely uncovered, because no rectangle side crosses its interior. Sum the true coordinate width times height of each marked cell.
  3. The two sample rectangles each have area 4 and overlap in one unit square. The marked-cell sum is therefore 4+4−1=7, without double-counting the overlap.

Why it works

All coverage boundaries belong to the compressed grid. Marking a cell is equivalent to some rectangle containing its entire interior. These disjoint cells partition the union except for zero-area boundaries, so summing their areas gives exactly the union area.

Complexity: O(N³) time in this straightforward implementation, with at most O(N²) cells marked per rectangle; O(N²) space. N≤100 keeps this small.

Watch out. Use coordinate differences as physical widths, not compressed index differences. Normalize corner order and permit degenerate rectangles.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
// Algorithm: Collect and sort all distinct x-coordinates and y-coordinates of rectangle sides.
using namespace std;
int main(){
    int count;
    cin>>count;
    vector<array<int,4>>rectangles(count);
    vector<int>xs,ys;
    for(auto&r:rectangles){
        cin>>r[0]>>r[1]>>r[2]>>r[3];
        if(r[0]>r[2]){
            swap(r[0],r[2]);
        }
        if(r[1]>r[3]){
            swap(r[1],r[3]);
        }
        xs.push_back(r[0]);
        xs.push_back(r[2]);
        ys.push_back(r[1]);
        ys.push_back(r[3]);
    }
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    sort(ys.begin(),ys.end());
    ys.erase(unique(ys.begin(),ys.end()),ys.end());
    vector<vector<bool>>covered(xs.size(),vector<bool>(ys.size(),false));
    for(const auto&r:rectangles){
        int left=lower_bound(xs.begin(),xs.end(),r[0])-xs.begin();
        int right=lower_bound(xs.begin(),xs.end(),r[2])-xs.begin();
        int bottom=lower_bound(ys.begin(),ys.end(),r[1])-ys.begin();
        int top=lower_bound(ys.begin(),ys.end(),r[3])-ys.begin();
        for(int x=left;x<right;x++){
            for(int y=bottom;y<top;y++){
                covered[x][y]=true;
            }
        }
    }
    long long area=0;
    for(size_t x=0;x+1<xs.size();x++){
        for(size_t y=0;y+1<ys.size();y++){
            if(covered[x][y]){
                area+=1LL*(xs[x+1]-xs[x])*(ys[y+1]-ys[y]);
            }
        }
    }
    cout<<area<<'\n';
}

Source: Arena Olimpiici ↗