Mobile

Análisis oficial 

Si podemos cubrir la carretera usando círculos de radio $r_1$, entonces también podemos cubrirla usando círculos de radio $r_2 > r_1$. Esto sugiere que hay que hacer búsqueda binaria sobre la respuesta.

Comprobar un radio

Si un círculo cubre una parte de una carretera, cubre un segmento. Usando el teorema de Pitágoras ($a^2 + b^2 = c^2$), podemos hallar las coordenadas de los extremos de cada uno de esos segmentos. Sea $s_i$ el segmento de la $i$-ésima torre.

Comprobar si un radio es bueno se reduce ahora a comprobar si la unión de estos segmentos es un único segmento que cubre por completo la carretera.

Podemos resolver esto en $\mathcal{O}(N \log N)$ ordenando los segmentos por su extremo izquierdo y luego fusionando cada segmento en la unión si intersecta la unión de los segmentos anteriores.

Lamentablemente, esto es un poco demasiado lento ($\mathcal{O}(N \log N \log L)$ en total) y solo obtiene 50 puntos.

Por suerte, ¡no hace falta ordenar los segmentos!

Una propiedad útil

¿Por qué haría falta ordenar los segmentos en primer lugar?

Imaginemos que tuviéramos tres segmentos $f$, $g$ y $h$ en ese orden en la lista sin ordenar. Observemos qué ocurre cuando estos segmentos se disponen como se muestra abajo:

Sin ordenar, $g$ no formaría parte de la unión porque $f \cap g = \emptyset$. Sin embargo, la unión real contiene los tres segmentos.

¿Pero qué pasa si $h$ cubre por completo a $g$?

En este caso, no importa que $g$ no forme parte de la unión, porque $f \cup g \cup h = f \cup h$ de todos modos.

Lo bueno de este problema en particular es que si tenemos el segmento $s_i$ después del segmento $s_j$ en la lista pero el extremo izquierdo de $s_i$ está a la izquierda del extremo izquierdo de $s_j$, entonces $s_i$ debe cubrir por completo a $s_j$.

¿Por qué es cierto? La única vez que tendremos el segmento $s_i$ después del segmento $s_j$ en la lista pero el extremo izquierdo de $s_i$ a la izquierda del de $s_j$ es cuando $x_i > x_j$ e $y_i < y_j$.

Claramente, $s_i$ cubre por completo a $s_j$. Por lo tanto, podemos aplicar nuestro algoritmo para una lista ordenada y seguir obteniendo la respuesta correcta.

Esto elimina el factor $\log N$ de la complejidad original, así que la complejidad final es $\mathcal{O}(N \log L)$, lo que alcanza para 100 puntos.

Implementación

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
 
pair<long long, long long> p[1000000];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, len;
	cin >> n >> len;
	for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
 
	double l = 0, r = 2.5e9;
	while (r - l > 1e-3) {
		double mid = (l + r) / 2, curr = 0;
		for (int i = 0; i < n; i++) {
			double delta = sqrt(mid * mid - p[i].y * p[i].y);
			double a = p[i].x - delta, b = p[i].x + delta;
			if (a <= curr) curr = max(curr, b);
		}
 
		if (curr >= len) r = mid;
		else l = mid;
	}
 
	cout << fixed << setprecision(4) << l;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
struct Point {
	double x, y;
};
 
/**
 * @return la intersección de la perpendicular que
 * cruza el punto medio de los Points a y b con la carretera
 */
double max_point(const Point &a, const Point &b) {
	return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * b.x - 2 * a.x);
}
/** @return la distancia euclidiana entre los puntos a y b */
double dist(const Point &a, const Point &b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
 
int main() {
	int n, l;
	cin >> n >> l;
 
	deque<Point> needed;
	for (int i = 0; i < n; i++) {
		Point cur;
		cin >> cur.x >> cur.y;
		cur.y = abs(cur.y);
 
		// siempre tomamos el de menor coordenada y
		if ((int)needed.size() && needed.back().x == cur.x) {
			if (cur.y >= needed.back().y) {
				continue;
			} else if (cur.y < needed.back().y) {
				needed.pop_back();
			}
		}
 
		// hallamos "cruces"
		while ((int)needed.size() > 1 &&
		       max_point(needed[(int)needed.size() - 2], needed.back()) >
		           max_point(needed.back(), cur)) {
			needed.pop_back();
		}
 
		needed.push_back(cur);
	}
 
	// fuera de rango
	while ((int)needed.size() > 1 && max_point(needed[0], needed[1]) < 0) {
		needed.pop_front();
	}
 
	while ((int)needed.size() > 1 &&
	       max_point(needed[(int)needed.size() - 2], needed.back()) > l) {
		needed.pop_back();
	}
 
	double ans = 0;
	for (int x = 0; x < (int)needed.size(); x++) {
		// obtenemos los puntos críticos de los que needed[x] se encarga
		Point left = {0, 0};
		Point right{(double)l, 0};
 
		if (x) { left.x = max_point(needed[x], needed[x - 1]); }
		if (x < (int)needed.size() - 1) {
			right.x = max_point(needed[x], needed[x + 1]);
		}
 
		if (left.x < 0 || right.x > l || right.x < 0 || left.x > l) { continue; }
 
		ans = max({ans, dist(needed[x], left), dist(needed[x], right)});
	}
 
	cout << fixed << setprecision(6) << ans << endl;
}