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.