Barrido (sweep line)

Tema: Geometría · temarios: Syllabus OCI · Syllabus IOI

📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.

Qué hace

Procesa eventos ordenados por una coordenada manteniendo una estructura activa; aquí, la longitud cubierta por una unión de intervalos.

Complejidad: O(n log n) por el ordenamiento de eventos.

Cuándo usarlo

Unión/intersección de intervalos o rectángulos, conteo de solapamientos, par más cercano, eventos en el tiempo.

Implementación recomendada (C++)

// Longitud cubierta por la unión de intervalos [l, r) mediante barrido de eventos.
long long union_length(vector<pair<long long,long long>> iv) {
    vector<pair<long long,int>> ev;
    for (auto& [l, r] : iv) { ev.push_back({l, +1}); ev.push_back({r, -1}); }
    sort(ev.begin(), ev.end());
    long long total = 0, prev = 0; int cov = 0;
    for (auto& [x, d] : ev) {
        if (cov > 0) total += x - prev;
        cov += d; prev = x;
    }
    return total;
}

⚠️ Notas

⚠️ Cuidado con los empates: al ordenar (x, delta) los cierres (-1) quedan antes que las aperturas (+1). Para longitud de unión con intervalos semiabiertos da igual, pero con intervalos cerrados [l,r] rompe el conteo — usa {r+1, -1} o invierte el criterio. Para áreas de rectángulos, el barrido va en una dimensión y mantiene un segment tree de cobertura en la otra. El patrón ‘evento +1/-1 ordenado’ es general y va mucho más allá de la geometría.

🔗 Relacionados