Línea de barrido

Introducción

Imaginar que se tiene una recta vertical que “barre” el plano de izquierda a derecha. Esa es la idea principal detrás de la línea de barrido.

Se podría pensar “un momento: ¿no es superineficiente llevar la cuenta de la línea de barrido en todas las posiciones posibles?” Y sería correcto. Sin embargo, en realidad no hace falta llevar la cuenta de la línea de barrido en todas las posiciones posibles, sino solo en las posiciones “críticas” (p. ej. puntos e intersecciones).

Recursos
Fuente	Recurso	Notas
CPH	30.1, 30.2 - Sweep Line Algorithms
TC	Line Sweep Algorithms

Restaurant Customers

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Restaurant Customers	Fácil	Sweep Line	Solución

Solución

La solución usa un enfoque de línea de barrido. Cada intervalo se convierte en dos eventos: $(a_i, +1)$ para una llegada y $(b_i, -1)$ para una salida. Esto produce $2N$ eventos en total.

Todos los eventos se ordenan por tiempo; si dos eventos coinciden, las salidas se procesan antes que las llegadas. Recorriendo la lista ordenada de izquierda a derecha, mantenemos un contador de clientes activos. El contador se incrementa en eventos de llegada y se decrementa en eventos de salida. El valor máximo alcanzado durante este recorrido es la respuesta.

Por ejemplo, los intervalos $(5,8), (2,4), (3,9)$ dan la secuencia de eventos $(2,+1), (3,+1), (4,-1), (5,+1), (8,-1), (9,-1)$ con contadores $1,2,1,2,1,0$ . El máximo es $2$ .

Crear los eventos toma $\mathcal{O}(N)$ , ordenarlos toma $\mathcal{O}(N \log N)$ , y el barrido es $\mathcal{O}(N)$ . Así, la complejidad total es $\mathcal{O}(N \log N)$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<pair<int, int>> events;
	for (int i = 0; i < n; i++) {
		int arrival, departure;
		cin >> arrival >> departure;
		events.push_back({arrival, +1});
		events.push_back({departure, -1});
	}
 
	sort(events.begin(), events.end());
 
	int active = 0;      // current number of customers
	int max_active = 0;  // maximum number of customers at any point of time
	for (auto &[time, change] : events) {
		active += change;
		max_active = max(max_active, active);
	}
	cout << max_active << "\n";
}

Par más cercano

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Kattis	Closest Pair	Normal	Sweep Line	en el módulo

Solución 1

Usaremos un algoritmo de divide y vencerás. Primero, ordenar los puntos por coordenada x. Ahora, sea $P$ el subarreglo de puntos en el paso actual. Luego, partir $P$ en dos grupos $L$ y $R$ que representan las mitades izquierda y derecha de $P$ . Sean $\delta_l$ y $\delta_r$ la respuesta de $L$ y $R$ respectivamente, y definir $\delta$ como $\min(\delta_l, \delta_r)$ .

Entonces $\delta$ es una cota superior de la respuesta. Si existe una respuesta más óptima, debe unir las dos mitades del arreglo (es decir, uno de sus extremos está en $L$ y el otro en $R$ ). Sea $mx$ la coordenada x de cualquier mediana de $P$ . Definir dos conjuntos $L'$ y $R'$ tales que $L' = \{p_i | x_i \leq mx, mx - x_i \leq \delta\}$ y

R' = \{p_i | x_i \geq mx, x_i - mx \leq \delta\}

Un algoritmo de emparejamiento por fuerza bruta que calcule $\texttt{dist}(p, q)$ para todo $p \in L'$ , $q \in R'$ tendría un tiempo de ejecución de peor caso de $(\frac n 2)^2 = \mathcal{O}(n^2)$ (recordar que $L'$ y $R'$ pueden tener hasta $\frac N 2$ puntos). Sin embargo, como estamos buscando distancias de a lo sumo $\delta$ , basta con que para cada $p \in L'$ se revisen todos los puntos $\{q | q \in R', p.y - \delta \leq q.y \leq p.y + \delta\}$ .

Se puede mostrar que para cada punto $p$ hay una cantidad constante de puntos que satisfacen esta propiedad. Como cada punto de $R'$ está al menos a distancia $\delta_r \geq \delta$ , disponer los puntos en el peor caso resultaría en 6 puntos en las esquinas y lados del rectángulo envolvente.

Disposición de peor caso de la caja envolvente

Para lograr la complejidad deseada de $\mathcal{O}(n)$ por capa, hay que poder obtener de forma eficiente los puntos ordenados tanto por coordenada x (para partir $P$ ) como por coordenada y (para el emparejamiento entre $L'$ y $R'$ ). Esto se puede lograr aprovechando el algoritmo tipo mergesort: ordenar por coordenada x al comienzo, y luego en cada paso mezclar las coordenadas y de forma recursiva.

Como cada paso ahora corre en tiempo lineal y hay un total de $\lceil \log n \rceil$ pasos, por el teorema maestro nuestra solución ahora corre en $\mathcal{O}(n\log n)$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
struct Point {
	long double x, y;
	bool operator<(const Point &other) {
		if (x == other.x) { return y < other.y; }
		return x < other.x;
	}
};
 
const pair<Point, Point> INF{{-1e9, -1e9}, {1e9, 1e9}};
 
long double dist(const pair<Point, Point> &a) {
	long double d1 = a.first.x - a.second.x;
	long double d2 = a.first.y - a.second.y;
	return sqrt(d1 * d1 + d2 * d2);
}
 
pair<Point, Point> get_closest_points(const pair<Point, Point> &a,
                                      const pair<Point, Point> &b) {
	return dist(a) < dist(b) ? a : b;
}
 
/**
 * Brute force for points with near
 * the median point in the sorted array
 */
pair<Point, Point> strip_solve(vector<Point> &points) {
	pair<Point, Point> ans = INF;
	for (int i = 0; i < (int)points.size(); i++) {
		for (int j = i + 1; j < (int)points.size() && j - i < 9; j++) {
			ans = get_closest_points(ans, {points[i], points[j]});
		}
	}
	return ans;
}
 
/** Solve the problem for range [l, r] */
pair<Point, Point> solve(vector<Point> &points, int l, int r) {
	if (l == r) { return INF; }
	int mid = (l + r) / 2;
 
	// The smallest distance in range [l, mid]
	pair<Point, Point> ans_left = solve(points, l, mid);
	// The smallest distance in range [mid+1, r]
	pair<Point, Point> ans_right = solve(points, mid + 1, r);
	pair<Point, Point> ans;
 
	ans = get_closest_points(ans_left, ans_right);
	long double delta = dist(ans);
 
	Point mid_point = points[mid];
	vector<Point> strip;
	for (int i = l; i < r; i++) {
		if (abs(points[i].x - mid_point.x) <= delta) { strip.push_back(points[i]); }
	}
	sort(strip.begin(), strip.end(),
	     [](Point a, Point b) { return a.y < b.y || (a.y == b.y && a.x < b.x); });
	return get_closest_points(ans, strip_solve(strip));
}
 
int main() {
	int n;
	while (scanf("%d", &n) && n > 0) {
		vector<Point> v;
		for (int i = 0; i < n; i++) {
			long double x, y;
			scanf("%Lf %Lf", &x, &y);
			v.push_back({x, y});
		}
		sort(v.begin(), v.end());
		pair<Point, Point> ans = solve(v, 0, v.size());
		printf("%0.2Lf %0.2Lf %0.2Lf %0.2Lf\n", ans.first.x, ans.first.y, ans.second.x,
		       ans.second.y);
	}
}

Solución 2

Extendiendo la Solución 1, podemos usar un conjunto en lugar de divide y vencerás. De nuevo, definimos $\delta$ como la distancia más corta entre dos puntos hasta el momento. Después de ordenar los puntos por coordenada x, iteramos sobre ellos manteniendo una ventana deslizante que contiene las coordenadas y de todos los puntos en $[x-\delta,x]$ .

Caja envolvente de la solución con conjunto y línea de barrido

Al visitar el punto $P$ , usamos el conjunto para considerar todos los puntos con coordenada y en $[P_y-\delta, P_y+\delta]$ . El conjunto contiene $[P_x-\delta, P_x]$ por cómo se mantiene como ventana deslizante. Ahora tenemos la misma caja envolvente que en la Solución 1, con a lo sumo 6 puntos adentro.

Para cada punto, recalculamos $\delta = \min(\delta, \delta_p)$ , y actualizamos nuestro conjunto en consecuencia. Cada punto se inserta y se elimina del conjunto a lo sumo una vez, así que el algoritmo da $\mathcal{O}(n\log n)$ .

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
using ld = long double;
 
int main() {
	int n;
	while (cin >> n && n > 0) {
		vector<pair<ld, ld>> points(n);
		for (auto &p : points) { cin >> p.first >> p.second; }
 
		sort(points.begin(), points.end());
 
		auto get_dist = [](const pair<ld, ld> &a, const pair<ld, ld> &b) -> ld {
			return (a.first - b.first) * (a.first - b.first) +
			       (a.second - b.second) * (a.second - b.second);
		};
 
		ld min_dist = LLONG_MAX;
		set<pair<ld, ld>> s = {{points[0].second, points[0].first}};
 
		array<ld, 4> ans;
		for (int i = 1, j = 0; i < points.size(); i++) {
 
			ld d = sqrt(min_dist);
			while (j < i && points[j].first < points[i].first - d) {
				s.erase({points[j].second, points[j].first});
				j++;
			}
 
			auto l = s.lower_bound({points[i].second - d, 0});
			auto r = s.upper_bound({points[i].second + d, 0});
 
			for (auto it = l; it != r; ++it) {
				ld d = get_dist(points[i], {it->second, it->first});
				if (min_dist > d) {
					min_dist = d;
					// ans = {points[i], {it->second, it->first}};
					ans = {points[i].first, points[i].second, it->second, it->first};
				}
			}
			s.insert({points[i].second, points[i].first});
		}
 
		cout << setprecision(2) << fixed << ans[0] << ' ' << ans[1] << ' ' << ans[2]
		     << ' ' << ans[3] << '\n';
	}
}

Segmentos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Silver	Cow Steeplechase II	Normal	Sweep Line	—

Solución - Cow Steeplechase II

Simplifiquemos un poco el problema y enfoquémonos en hallar cualquier par de segmentos que se superponen.

Para hallar un par de segmentos que se superponen, usar un enfoque de línea de barrido barriendo una recta vertical a través de la escena de izquierda a derecha, deteniéndose en cada extremo de segmento.

Simulamos esto ordenando todos los extremos de segmentos por $x$ y recorriendo el arreglo ordenado (llamado ‘events’ en el código de abajo). Mientras barrimos, llevamos la cuenta de los segmentos activos usando un conjunto (llamado ‘active_segments’ en el código de abajo). Cuando golpeamos el punto inicial de un segmento, lo agregamos al conjunto activo, y lo quitamos del conjunto activo cuando golpeamos el punto final de un segmento.

Insertar o eliminar los segmentos activos del conjunto toma $\mathcal{O}(\log n)$ por operación.

El conjunto activo de segmentos está ordenado por coordenada $y$ . Si dos segmentos se superponen, son adyacentes en el conjunto, así que cada vez que insertamos o eliminamos un segmento, comprobamos si los segmentos adyacentes se superponen.

Aquí hay una animación de cómo funciona:

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$ .

C++


#include <bits/stdc++.h>
using namespace std;
 
long long sweep_line_x;
 
// BeginCodeSnip{Point Structure}
struct Point {
	long long x, y, segment_idx;
	bool operator<(const Point &other) {
		return x == other.x ? y < other.y : x < other.x;
	}
};
int operator*(Point p1, Point p2) { return sign(p1.x * p2.y - p1.y * p2.x); }
 
Point operator-(Point p1, Point p2) {
	Point p = {p1.x - p2.x, p1.y - p2.y};
	return p;
}
// EndCodeSnip
 
// BeginCodeSnip{Segment Structure}
struct Segment {
	long long a, b;
	long long x, y;
	long long idx;
};
 
bool operator<(Segment a, Segment b) {
	return a.idx != b.idx && coordinate(a) <= coordinate(b);
}
 
bool operator==(Segment a, Segment b) { return a.idx == b.idx; }
// EndCodeSnip
 
int sign(long long x) {
	if (x == 0) {
		return 0;
	} else {
		return x < 0 ? -1 : +1;
	}
}
 
double coordinate(Segment a) {
	if (a.a == a.x) { return a.b; }
	return a.b + (a.y - a.b) * (sweep_line_x - a.a) / (a.x - a.a);
}
 
/*
 * To check if two segments intersect we will use the
 * signed area of the ABC triangle. This can be derived
 * from the cross product of the vectors AB and AC.
 */
bool intersect(Segment a, Segment b) {
	Point p1 = {a.a, a.b}, q1 = {a.x, a.y}, p2 = {b.a, b.b}, q2 = {b.x, b.y};
	return ((q2 - p1) * (q1 - p1)) * ((q1 - p1) * (p2 - p1)) >= 0 &&
	       ((q1 - p2) * (q2 - p2)) * ((q2 - p2) * (p1 - p2)) >= 0;
}
 
long long orientation(Point a, Point b, Point c) {
	return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
 
int main() {
	ifstream in("cowjump.in");
	int n;
	in >> n;
	vector<Segment> segments;
	vector<Point> events;
	for (int i = 0; i < n; i++) {
		int a, b, x, y;
		in >> a >> b >> x >> y;
 
		segments.push_back({a, b, x, y, i});
		events.push_back({a, b, i});
		events.push_back({x, y, i});
	}
 
	sort(events.begin(), events.end());
 
	// Keep track of active segments
	set<Segment> active_segments;
 
	// The two overlapping segments
	int first_segment, second_segment;
	for (int i = 0; i < 2 * n; i++) {
		first_segment = events[i].segment_idx;
		sweep_line_x = events[i].x;
		// Check if the point is the end or the beginning of a segment
		auto it = active_segments.find(segments[first_segment]);
 
		if (it != active_segments.end()) {
			// Ending segment & Check the intersection of the segments above and
 
			auto after = next(it), before = it;
			if (before != active_segments.begin() && after != active_segments.end()) {
				before--;
				if (intersect(segments[before->idx], segments[after->idx])) {
					first_segment = before->idx;
					second_segment = after->idx;
					break;
				}
			}
			active_segments.erase(it);
		} else {
			// New segment & check for intersection
			it = active_segments.lower_bound(segments[first_segment]);
 
			// Check the intersection of the segments above and below
			if (it != active_segments.end() &&
			    intersect(segments[first_segment], *it)) {
				second_segment = it->idx;
				break;
			}
			if (it != active_segments.begin()) {
				it--;
				if (intersect(segments[it->idx], segments[first_segment])) {
					second_segment = it->idx;
					break;
				}
			}
			active_segments.insert(segments[first_segment]);
		}
	}
 
	if (first_segment > second_segment) { swap(first_segment, second_segment); }
 
	// Which segment of the two is the answer
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (i != second_segment && intersect(segments[i], segments[second_segment])) {
			ans++;
		}
	}
 
	ofstream("cowjump.out") << (ans > 1 ? second_segment + 1 : first_segment + 1);
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
Old Silver	Square Overlap	Fácil	Sweep Line	—
Old Gold	Hill Walk	Normal	Sweep Line	—
COI	2017 - Plahte	Difícil	Sweep Line	Solución
CEOI	2006 - Walk	Difícil	Sweep Line	Solución
CEOI	★ 2020 - Roads	Muy difícil	Sweep Line	—
Baltic OI	2014 - Demarcation	Muy difícil	Sweep Line	—

MST de Manhattan

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Kattis	Grid MST	Normal	Manhattan MST	—

Solución - Grid MST

La observación clave es que, aunque hay muchos puntos, están repartidos en una superficie bastante pequeña. Por esto, en lugar de usar el algoritmo de Kruskal o el de Prim, podemos usar Dijkstra. Empezando desde un punto arbitrario, ejecutamos el algoritmo de Dijkstra con una cola de prioridad que ordenará los puntos por su distancia al MST.

Implementación

Complejidad temporal: $\mathcal{O}(S^3\log S)$ , donde $S$ es el tamaño de la grilla

C++


#include <bits/stdc++.h>
using namespace std;
 
const int GRID_SZ = 1000;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
 
int main() {
	int n;
	cin >> n;
 
	// The distance from the starting point
	vector<vector<int>> d(GRID_SZ, vector<int>(GRID_SZ, -1));
	// mat[x][y] = if (x, y) point is in the input;
	vector<vector<bool>> mat(GRID_SZ, vector<bool>(GRID_SZ));
 
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
	               greater<pair<int, pair<int, int>>>>
	    pq;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		mat[x][y] = 1;
		if (i == 0) {
			d[x][y] = 0;
			pq.push({0, {x, y}});
		}
	}
 
	auto inside = [&](int x, int y) {
		return 0 <= x && 0 <= y && x < GRID_SZ && y < GRID_SZ;
	};
 
	// Dijkstra's algorithm
	int ans = 0;
	while (!pq.empty()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		int dist = pq.top().first;
		pq.pop();
 
		if (dist != d[x][y]) { continue; }
		if (mat[x][y]) {
			mat[x][y] = 0;
			ans += dist;
			d[x][y] = 0;
			pq.push({0, {x, y}});
			if (dist) { continue; }
		}
 
		for (int dir = 0; dir < 4; dir++) {
			int newx = x + dx[dir];
			int newy = y + dy[dir];
			// Check if it's a new point or if the distance has improved
			if (inside(newx, newy) &&
			    (d[newx][newy] == -1 || dist + 1 < d[newx][newy])) {
				d[newx][newy] = dist + 1;
				pq.push({d[newx][newy], {newx, newy}});
			}
		}
	}
 
	cout << ans << endl;
}

Problemas

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSA	The Sprawl	Difícil	Manhattan MST	—

Barrido radial

En lugar de una recta vertical que barre el plano de izquierda a derecha, el barrido radial (radial sweep) involucra un rayo que rota alrededor de un punto central (como una pantalla de radar):

Radar screen gif

En este caso, ordenamos puntos/eventos por su rumbo (bearing) en lugar de por sus coordenadas x e y. Aparte de eso, la mecánica es la misma que la de la línea de barrido normal.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	IOI	2003 - Seeing the Boundary	Fácil	Radial Sweep	—

Solución - Seeing the Boundary

En este problema hay tres tipos de eventos: cuando nuestro rayo golpea un poste de la cerca, entra en una roca, o sale de una roca.

El segundo y el tercer tipo de eventos se pueden hallar para cada roca ordenando los rayos a sus vértices por rumbo y luego tomando los dos extremos de la lista ordenada. Estos dos rayos son las dos tangentes a la roca.

Luego podemos hacer un barrido radial para hallar los postes de la cerca que Farmer Don puede ver: estos postes son simplemente aquellos en los que la cantidad de eventos de tipo 2 y tipo 3 que hemos procesado hasta el momento es igual.

Observar que algunas optimizaciones (p. ej. no construir la lista de postes de forma explícita) pueden ser necesarias para obtener 100 puntos.

Implementación

Complejidad temporal: $\mathcal O(N + Rp_i \log R)$

C++


#include <bits/stdc++.h>
#define x first
#define y second
typedef long long ll;
using namespace std;
 
const double PI = 4 * atan(1);
 
struct Event {
	short type, id;
	pair<ll, ll> loc;
};
 
pair<ll, ll> origin, polygon[22];
 
// Cross product
ll cross(pair<ll, ll> a, pair<ll, ll> b) {
	return (a.y - origin.y) * (b.x - origin.x) - (a.x - origin.x) * (b.y - origin.y);
}
 
// Which half of the plane some point lies in
int half(pair<ll, ll> p) {
	if (p.x != origin.x) return (p.x < origin.x) - (p.x > origin.x);
	return (p.y < origin.y) - (p.y > origin.y);
}
 
// Custom comparator to sort by bearing
bool operator<(Event a, Event b) {
	int ah = half(a.loc), bh = half(b.loc);
	if (ah == bh) {
		ll c = cross(a.loc, b.loc);
		if (c == 0) return a.type > b.type;
		return c > 0;
	}
	return ah < bh;
}
 
// Generates the next fence post in clockwise order
Event get_next_post(Event curr, int n) {
	if (curr.loc.x == n) {
		if (curr.loc.y) return {0, 0, {n, curr.loc.y - 1}};
		return {0, 0, {n - 1, 0}};
	} else if (!curr.loc.x) {
		if (curr.loc.y != n) return {0, 0, {0, curr.loc.y + 1}};
		return {0, 0, {1, n}};
	} else if (curr.loc.y == n) {
		if (curr.loc.x != n) return {0, 0, {curr.loc.x + 1, n}};
		return {0, 0, {n, n - 1}};
	} else {
		if (curr.loc.x) return {0, 0, {curr.loc.x - 1, 0}};
		return {0, 0, {0, 1}};
	}
}
 
vector<Event> events;
bool before[44444];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, r;
	cin >> n >> r >> origin.x >> origin.y;
 
	for (int i = 0; i < r; i++) {
		int m;
		cin >> m;
		for (int j = 0; j < m; j++) cin >> polygon[j].x >> polygon[j].y;
		// Sort the polygon's vertices to find the 2 "tangents" from the origin
		sort(polygon, polygon + m,
		     [](pair<ll, ll> a, pair<ll, ll> b) { return cross(a, b) > 0; });
		events.push_back({1, i, polygon[0]});
		events.push_back({-1, i, polygon[m - 1]});
	}
	sort(events.begin(), events.end());
 
	int active = 0;
	// Do an initial sweep to handle rocks containing the ray with bearing 0
	// This way, `active` won't be messed up
	for (Event i : events) {
		if (i.type == 1) before[i.id] = true;
		if (i.type == -1 && !before[i.id]) active++;
	}
 
	int ans = 0, ptr = 0;
	Event curr_post = {0, 0, {origin.x, n}};
	for (Event i : events) {
		while (ptr != 4 * n && curr_post < i) {
			// If there are no rocks that our current ray intersects...
			if (!active) ans++;
			ptr++;
			curr_post = get_next_post(curr_post, n);
		}
 
		if (i.type == 1) active++;
		else active--;
	}
	if (!active) ans += 4 * n - ptr;
 
	cout << ans;
	return 0;
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CEOI	2006 - Antenna	Fácil	Binary Search, Radial Sweep	Solución
POI	2018 - Stone	Normal	Radial Sweep	—
APIO	2010 - Signaling	Difícil	Radial Sweep	—
JOI	2017 - Dragon 2	Difícil		Solución