El concepto de línea de barrido (sweep line) es una técnica fundamental en la geometría computacional. Consiste en desplazar una línea imaginaria (generalmente vertical u horizontal) a través del plano, deteniéndose en puntos específicos donde ocurren eventos relevantes para procesar datos de manera eficiente.

Unión de Áreas Rectangulares

El problema consiste en calcular el área total ocupada por $N$ rectángulos en un plano cartesiano, donde cada lado es paralelo a los ejes coordenados. Dado que los rectángulos pueden solaparse, el área de las intersecciones debe contabilizarse una sola vez.

Para resolver esto, podemos proyectar el problema en una dimensión. Si consideramos una línea de barrido vertical que se mueve de izquierda a derecha, el área total es la suma de las áreas de las franjas verticales delimitadas por los bordes de los rectángulos. El "ancho" de cada franja es la diferencia entre las coordenadas $x$ consecutivas, y la "altura" es la longitud de la unión de los segmentos verticales activos en ese intervalo.

Para mantener la longitud de la unión de segmentos de forma eficiente, utilizamos un Árbol de Segmentos (Segment Tree). Si las coordenadas $y$ son muy grandes, aplicamos discretización previa. El árbol almacenará cuántas veces está cubierto un intervalo y la longitud total cubierta actual.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Evento {
    int x, y_min, y_max, tipo;
    bool operator<(const Evento& otro) const {
        return x < otro.x;
    }
};

struct NodoSegmento {
    int cobertura;
    ll longitud;
};

const int MAX_N = 200005;
NodoSegmento arbol[MAX_N * 8];
int coordenadas_y[MAX_N * 2];

void actualizar(int nodo, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        arbol[nodo].cobertura += val;
    } else {
        int mid = (l + r) / 2;
        if (ql <= mid) actualizar(nodo * 2, l, mid, ql, qr, val);
        if (qr > mid) actualizar(nodo * 2 + 1, mid + 1, r, ql, qr, val);
    }
    
    if (arbol[nodo].cobertura > 0) {
        arbol[nodo].longitud = coordenadas_y[r + 1] - coordenadas_y[l];
    } else if (l != r) {
        arbol[nodo].longitud = arbol[nodo * 2].longitud + arbol[nodo * 2 + 1].longitud;
    } else {
        arbol[nodo].longitud = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Evento> eventos;
    int contador_y = 0;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        eventos.push_back({x1, y1, y2, 1});
        eventos.push_back({x2, y1, y2, -1});
        coordenadas_y[contador_y++] = y1;
        coordenadas_y[contador_y++] = y2;
    }

    sort(coordenadas_y, coordenadas_y + contador_y);
    int m = unique(coordenadas_y, coordenadas_y + contador_y) - coordenadas_y;
    sort(eventos.begin(), eventos.end());

    ll area_total = 0;
    for (int i = 0; i < eventos.size(); ++i) {
        if (i > 0) {
            area_total += arbol[1].longitud * (eventos[i].x - eventos[i - 1].x);
        }
        int pos_min = lower_bound(coordenadas_y, coordenadas_y + m, eventos[i].y_min) - coordenadas_y;
        int pos_max = lower_bound(coordenadas_y, coordenadas_y + m, eventos[i].y_max) - coordenadas_y;
        actualizar(1, 0, m - 2, pos_min, pos_max - 1, eventos[i].tipo);
    }

    cout << area_total << endl;
    return 0;
}

Análisis de Flujo en Paneles Horizontales

Consideremos un sistema de $N$ paneles horizontales a diferentes alturas. El agua fluye desde la parte superior de la pared hacia abajo. El flujo entre dos paneles $u$ y $v$ es posible si no hay paneles intermedios que bloqueen el paso directo, existe un solapamiento horizontal y el panel $u$ está por encima de $v$. La capacidad del flujo es el ancho del solapamiento.

Para resolver este problema, utilizamos nuevamente la línea de barrido. Al barrer horizontalmente las coordenadas $x$ de los extremos de los paneles, mantenemos un conjunto ordenado (como std::set) de los paneles activos ordenados por su altura $h$.

Cuando encontramos el inicio de un panel, identificamos sus vecinos inmediatos supreiores e inferiores en el conjunto. Estos son los candidatos para establecer conexiones de flujo. Al finalizar, el problema se transforma en encontrar la ruta de máxima capacidad en un Grafo Acíclico Dirigido (DAG) mediante programación dinámica.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

struct Panel {
    int h, l, r, id;
};

struct Punto {
    int x, id, tipo; 
    bool operator<(const Punto& o) const {
        if (x != o.x) return x < o.x;
        return tipo < o.tipo; 
    }
};

const int INF = 2e9;
const int MAX_P = 100005;
Panel p[MAX_P];
int f[MAX_P];
vector<int> adj[MAX_P];
map<pair<int, int>, bool> bloqueado;

int main() {
    int n, pared_h;
    cin >> n >> pared_h;

    vector<Punto> puntos;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i].h >> p[i].l >> p[i].r;
        p[i].id = i;
        puntos.push_back({p[i].l, i, 0});
        puntos.push_back({p[i].r, i, 1});
    }

    // Paneles especiales: Techo y Suelo
    p[0] = {0, -INF, INF, 0};
    p[n + 1] = {pared_h, -INF, INF, n + 1};
    
    sort(puntos.begin(), puntos.end());
    set<pair<int, int>> activos;
    activos.insert({0, 0});
    activos.insert({pared_h, n + 1});
    adj[n + 1].push_back(0);

    for (auto& pt : puntos) {
        int i = pt.id;
        if (pt.tipo == 0) {
            auto it = activos.upper_bound({p[i].h, i});
            int arriba = it->second;
            int abajo = prev(it)->second;
            
            bloqueado[{arriba, abajo}] = true;
            adj[arriba].push_back(i);
            adj[i].push_back(abajo);
            activos.insert({p[i].h, i});
        } else {
            activos.erase({p[i].h, i});
        }
    }

    vector<int> orden(n + 2);
    for (int i = 0; i <= n + 1; ++i) orden[i] = i;
    sort(orden.begin(), orden.end(), [](int a, int b) {
        return p[a].h > p[b].h;
    });

    f[n + 1] = INF * 1.5; // Representa flujo infinito inicial
    for (int u : orden) {
        for (int v : adj[u]) {
            if (bloqueado.count({u, v})) continue;
            int capacidad = min(p[u].r, p[v].r) - max(p[u].l, p[v].l);
            f[v] = max(f[v], min(f[u], capacidad));
        }
    }

    cout << f[0] << endl;
    return 0;
}