Algorithm Overview

The sweep line algorithm efficiently computes the union area and perimeter of multiple overlapping rectangles. By simulating a line scanning across the plane and processing horizontal and vertical segments, it achieves O(n log n) time complexity.

Area Union Calculation

Problem Statement

Given n potentially overlapping rectangles, calculate thier total union area (sum of areas minus overlapping regions).

Algorithm Approach

Traditional inclusion-exclusion methods become impractical for implementation. Instead, we transform the problem by dividing the plane in to non-overlapping horizontal segments.

Consider a horizontal line scanning from bottom to top. When encountering rectangle edges, we process them to accumulate area contributions. The key insight is that between consecutive horizontal edges, the covered width remains constant.

Implementation Details

We address several challenges:

• Coordinate Discretization: x-coordinates may not be integers, requiring discretization
• Spatial Optimization: Store only necessary endpoints
• Temporal Optimization: Use segment trees for efficiant range queries

We represent vertical edges as points on the x-axis, transforming the 2D problem into 1D interval operations. For each interval [l, r], we maintain:

• Interval endpoints
• Complete coverage status
• Total covered length

Algorithm Flow

1. Store horizontal edges with their y-coordinates and weights (+1 for bottom edges, -1 for top edges)
2. Sort edges by y-coordinate
3. Discretize x-coordinates
4. Process each edge: update segment tree with edge weight and calculate area contribution

Special handling ensures single-point segments don't cause errors by representing interval [l, r] as [l, r+1] in the segment tree.

Code Implementation

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

const int MAXN = 100005;

struct SegmentNode {
    int left, right, coverage;
    long long covered_length;
};

struct HorizontalEdge {
    long long x_start, x_end, y;
    int weight;
    bool operator<(const HorizontalEdge& other) const {
        return y < other.y;
    }
};

SegmentNode seg_tree[4 * MAXN];
HorizontalEdge edges[2 * MAXN];
long long x_coords[2 * MAXN];

void update_node(int idx) {
    if (seg_tree[idx].coverage > 0) {
        seg_tree[idx].covered_length = x_coords[seg_tree[idx].right + 1] - x_coords[seg_tree[idx].left];
    } else {
        seg_tree[idx].covered_length = seg_tree[2*idx].covered_length + seg_tree[2*idx+1].covered_length;
    }
}

void build_tree(int idx, int l, int r) {
    seg_tree[idx].left = l;
    seg_tree[idx].right = r;
    if (l == r) {
        seg_tree[idx].covered_length = seg_tree[idx].coverage = 0;
        return;
    }
    int mid = (l + r) / 2;
    build_tree(2*idx, l, mid);
    build_tree(2*idx+1, mid+1, r);
    update_node(idx);
}

void modify_tree(int idx, long long l_bound, long long r_bound, int delta) {
    if (x_coords[seg_tree[idx].right + 1] <= l_bound || x_coords[seg_tree[idx].left] >= r_bound) {
        return;
    }
    if (x_coords[seg_tree[idx].left] >= l_bound && x_coords[seg_tree[idx].right + 1] <= r_bound) {
        seg_tree[idx].coverage += delta;
        update_node(idx);
        return;
    }
    modify_tree(2*idx, l_bound, r_bound, delta);
    modify_tree(2*idx+1, l_bound, r_bound, delta);
    update_node(idx);
}

int main() {
    int rect_count;
    cin >> rect_count;
    
    int edge_count = 0;
    for (int i = 0; i < rect_count; i++) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        x_coords[edge_count] = x1;
        x_coords[edge_count + 1] = x2;
        
        edges[edge_count] = {x1, x2, y1, 1};
        edges[edge_count + 1] = {x1, x2, y2, -1};
        edge_count += 2;
    }
    
    sort(edges, edges + edge_count);
    sort(x_coords, x_coords + edge_count);
    int unique_x = unique(x_coords, x_coords + edge_count) - x_coords;
    
    build_tree(1, 0, unique_x - 2);
    
    long long total_area = 0;
    for (int i = 0; i < edge_count - 1; i++) {
        modify_tree(1, edges[i].x_start, edges[i].x_end, edges[i].weight);
        total_area += seg_tree[1].covered_length * (edges[i+1].y - edges[i].y);
    }
    
    cout << total_area << endl;
    return 0;
}

Perimeter Union Calculation

Problem Statement

Calculate the total perimeter of the union of n rectangles.

Algorithm Approach

We extend the area calculation approach to track perimeter contributions. The perimeter consists of horizontal and vertical segments exposed in the final union.

Implementation Strategy

The segment tree maintains additional information:

• Left and right endpoint coverage status
• Number of continuous horizontal segments
• Total covered length
• Coverage count

Horizontal perimeter contributions come from changes in covered width between scan lines. Vertical perimeter contributions equal the number of horizontal segments multiplied by the height difference between scan lines.

Code Implementation

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

const int MAXN = 100005;

struct PerimeterNode {
    int left, right;
    int seg_length, coverage, seg_count;
    bool left_covered, right_covered;
};

struct Edge {
    int x_start, x_end, y;
    int weight;
    bool operator<(const Edge& other) const {
        if (y == other.y) return weight > other.weight;
        return y < other.y;
    }
};

PerimeterNode perimeter_tree[4 * MAXN];
Edge perimeter_edges[2 * MAXN];
int perimeter_x[2 * MAXN];

void perimeter_update(int idx) {
    if (perimeter_tree[idx].coverage > 0) {
        perimeter_tree[idx].seg_length = perimeter_x[perimeter_tree[idx].right + 1] - perimeter_x[perimeter_tree[idx].left];
        perimeter_tree[idx].left_covered = perimeter_tree[idx].right_covered = true;
        perimeter_tree[idx].seg_count = 1;
    } else {
        perimeter_tree[idx].seg_length = perimeter_tree[2*idx].seg_length + perimeter_tree[2*idx+1].seg_length;
        perimeter_tree[idx].left_covered = perimeter_tree[2*idx].left_covered;
        perimeter_tree[idx].right_covered = perimeter_tree[2*idx+1].right_covered;
        perimeter_tree[idx].seg_count = perimeter_tree[2*idx].seg_count + perimeter_tree[2*idx+1].seg_count;
        if (perimeter_tree[2*idx].right_covered && perimeter_tree[2*idx+1].left_covered) {
            perimeter_tree[idx].seg_count--;
        }
    }
}

void build_perimeter_tree(int idx, int l, int r) {
    perimeter_tree[idx].left = l;
    perimeter_tree[idx].right = r;
    if (l == r) {
        perimeter_tree[idx].seg_count = perimeter_tree[idx].coverage = perimeter_tree[idx].seg_length = 0;
        perimeter_tree[idx].left_covered = perimeter_tree[idx].right_covered = false;
        return;
    }
    int mid = (l + r) / 2;
    build_perimeter_tree(2*idx, l, mid);
    build_perimeter_tree(2*idx+1, mid+1, r);
    perimeter_update(idx);
}

void update_perimeter(int idx, int l_bound, int r_bound, int delta) {
    if (perimeter_x[perimeter_tree[idx].right + 1] <= l_bound || perimeter_x[perimeter_tree[idx].left] >= r_bound) {
        return;
    }
    if (perimeter_x[perimeter_tree[idx].left] >= l_bound && perimeter_x[perimeter_tree[idx].right + 1] <= r_bound) {
        perimeter_tree[idx].coverage += delta;
        perimeter_update(idx);
        return;
    }
    update_perimeter(2*idx, l_bound, r_bound, delta);
    update_perimeter(2*idx+1, l_bound, r_bound, delta);
    perimeter_update(idx);
}

int main() {
    int n;
    cin >> n;
    
    int edge_idx = 0;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        
        perimeter_x[edge_idx] = x1;
        perimeter_x[edge_idx + 1] = x2;
        
        perimeter_edges[edge_idx] = {x1, x2, y1, 1};
        perimeter_edges[edge_idx + 1] = {x1, x2, y2, -1};
        edge_idx += 2;
    }
    
    sort(perimeter_edges, perimeter_edges + edge_idx);
    sort(perimeter_x, perimeter_x + edge_idx);
    int unique_count = unique(perimeter_x, perimeter_x + edge_idx) - perimeter_x;
    
    build_perimeter_tree(1, 0, unique_count - 2);
    
    int total_perimeter = 0;
    int previous_length = 0;
    
    for (int i = 0; i < edge_idx - 1; i++) {
        update_perimeter(1, perimeter_edges[i].x_start, perimeter_edges[i].x_end, perimeter_edges[i].weight);
        total_perimeter += abs(perimeter_tree[1].seg_length - previous_length);
        previous_length = perimeter_tree[1].seg_length;
        total_perimeter += 2 * perimeter_tree[1].seg_count * (perimeter_edges[i+1].y - perimeter_edges[i].y);
    }
    
    total_perimeter += perimeter_edges[edge_idx-1].x_end - perimeter_edges[edge_idx-1].x_start;
    cout << total_perimeter << endl;
    
    return 0;
}