---
tags: geometry, sweep-line
---

# Sweep line

## Definición
Es una técnica de geometría computacional que usa el concepto de una línea que va barriendo (haciendo *sweep*) todo el plano y se va deteniendo en algunos lugares de interés. Usualmente la línea es vertical y se va a ir moviendo desde $x=-\infty$ hasta $x=\infty$. En términos prácticos no la podemos mover de forma continua ya que hay infinitos puntos, por lo que solo la vamos a mover de forma discreta en los lugares de interés, a los que llamaremos *eventos*.

Lo mínimo que esos eventos necesitan guardar es el tiempo en el que ocurren, y la forma usual de procesarlos es ordenarlos por dicho tiempo de menor a mayor, iterar por todos ellos y mantener cierta información global relativa al problema que irá cambiando entre evento y evento.

## Problemas

### [Intersección de segmentos alineados a los ejes](https://omegaup.com/arena/problem/interseccionsegmentos/#problems)

Tenemos $n$ segmentos en el plano ($1 \leq n \leq 10^5$), cada uno dado por sus puntos de inicio $a_i$ y fin $b_i$ para $1 \leq i \leq n$ y $a_i \neq b_i$. Estos segmentos solo pueden ser horizontales o verticales: es decir, si $a_i=(x_1,y_1)$ y $b_i=(x_2,y_2)$ se cumple que $x_1=x_2$ (vertical) o $y_1=y_2$ (horizontal). El problema es hallar el número total de intersecciones entre todos los segmentos. Se garantiza que todas las intersecciones existentes siempre serán entre un segmento horizontal y otro vertical.

La forma cuadrática de resolverlo es intentar intersectar cada par de segmentos, y si sí hay intersección, sumar 1 a la respuesta.

Para resolverlo usando sweep line vamos a mover una línea vertical infinita desde la izquierda que va a ir tocando los segmentos. Definiremos tres tipos de eventos:
- Evento tipo $\texttt{a}$: ocurrirá cuando la línea toque el extremo izquierdo de un segmento horizontal. Se puede ver como el momento en el que la línea *entra* al segmento.
- Evento tipo $\texttt{c}$: ocurrirá cuando la línea toque el extremo derecho de un segmento horizontal. Se puede ver como el momento en el que la línea *sale* del segmento.
- Evento tipo $\texttt{b}$: ocurrirá cuando la línea coincida con un segmento vertical.

Los tres tipos de evento necesitan guardar en qué tiempo ocurren, o sea, en qué coordenada en $x$ la línea los toca. Además, cada evento va a almacenar su segmento asociado.

Por lo tanto, por cada segmento horizontal vamos a crear dos eventos $\texttt{a}$ y $\texttt{c}$, y por cada segmento vertical un evento $\texttt{b}$.

Ahora viene la parte de procesamiento: ya que ordenamos todos los eventos por la coordenada en $x$ en la que ocurren; llevaremos una estructura de datos global que almacene los **segmentos activos**, o sea, los segmentos **horizontales** que la línea está tocando actualmente. Al principio la estructur estará vacía. Luego, hacemos lo siguiente por cada evento:
- Si el evento es de tipo $\texttt{a}$ introducimos su segmento horizontal asociado.
- Si el evento es de tipo $\texttt{c}$ borramos su segmento horizontal asociado.
- Los eventos de tipo $\texttt{b}$ son los que van a incrementar el número de intersecciones: la idea es ver con cuántos segmentos horizontales activos se cruza el segmento vertical asociado. Supongamos que el segmento vertical tiene rango $y_1 \leq y \leq y_2$, entonces vamos hacer un *range query* en nuestra estructura de datos que nos diga cuántos segmentos horizontales tienen su $y$ entre $y_1$ y $y_2$, e incrementamos la respuesta.

Se puede ver que la complejidad dependerá de qué tan eficiente sea nuestra estructura de datos con las queries. Si hacemos las inserciones y eliminaciones de forma bruta, la complejidad sigue siendo $O(n^2)$; pero si usamos un *order statistic set* (estructura que permite inserciones, eliminaciones y queries de lower bound en tiempo logarítmico), obtenemos una complejidad total de $O(n \log n)$.

**Preguntas**:
- ¿Cómo ordeno dos eventos que ocurren al mismo tiempo?

Implementación:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using lli = long long int;

struct segment{
	// if segment is horizontal, [start, end] is the range in "x", and axis is the common value of "y"
	// if segment is vertical, [start, end] is the range in "y", and axis is the common value of "x"
	int start, end, axis;
	segment(): start(0), end(0), axis(0) {}
	segment(int start, int end, int axis): start(start), end(end), axis(axis) {}

	// lexicographic order by (axis, start, end)
	bool operator<(const segment& s) const{
		if(axis != s.axis) return axis < s.axis;
		if(start != s.start) return start < s.start;
		return end < s.end;
	}
};

struct event{
	int p;      // position in "x" when this event
	char t;     // type of event: a (horizontal segment starts), b (vertical segment matches with sweeping line), c (horizontal segment ends)
	segment s;  // associated segment to this event
	event(): p(0), t(0){}
	event(int p, char t, segment s): p(p), t(t), s(s) {}

	// If events occur at the same time, sort by type of event. Otherwise, sort by the time when they occur.
	bool operator<(const event& e) const{
		if(p == e.p) return t < e.t;
		return p < e.p;
	}
};

typedef tree<segment, null_type, less<segment>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int xi, yi, xf, yf;
	vector<event> events;
	for(int i = 0; i < n; ++i){
		cin >> xi >> yi >> xf >> yf;
		if(yi == yf){ // horizontal segment
			if(xi > xf) swap(xi, xf); // ensure that starting point is on the left
			events.emplace_back(xi, 'a', segment(xi, xf, yi)); //start
			events.emplace_back(xf, 'c', segment(xi, xf, yi)); //end
		}else if(xi == xf){ // vertical segment
			if(yi > yf) swap(yi, yf); // ensume that starting point is on the bottom
			events.emplace_back(xi, 'b', segment(yi, yf, xi)); //vertical line
		}else{
			// no deberia ocurrir
		}
	}
	sort(events.begin(), events.end());
	ordered_set active;
	lli cnt = 0;
	for(const event& e : events){
		if(e.t == 'a') active.insert(e.s);
		else if(e.t == 'c') active.erase(e.s);
		else if(e.t == 'b'){
			// count hoy many active horizontal segments have height in range [e.s.start, e.s.end] -->
			// e.s.start <= y <= e.s.end --> y <= e.s.end , y >= e.s.start
			cnt += active.order_of_key(segment(0, 0, e.s.end + 1)) - active.order_of_key(segment(0, 0, e.s.start));
		}
	}
	cout << cnt << "\n";
	return 0;
}

[**Ejemplo interactivo**](https://www.geogebra.org/classic/m837afvt)

### Par de puntos más cercanos

### Área de unión de rectángulos

## Referencias
- https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/
- https://www.cs.mcgill.ca/~cs251/ClosestPair/proofbox.html
-