Skip to Content
CTRL K

Three Base Stations

Pista 1

¿Y si nos dieran dd y nos pidieran calcular si es posible cubrir todas las casas?

Pista 2

Miremos solo una casa. Tiene que ir una estación a algún lugar dentro de su alcance. ¿Dónde es el mejor lugar para ponerla?

Solución

Explicación

Hacemos búsqueda binaria sobre la respuesta.

Consideremos la casa más a la izquierda. Tenemos que colocar una estación dentro del alcance de esta casa. Como no hay casas a la izquierda, y por lo tanto no hay motivo para que el alcance de la estación se extienda hacia la izquierda, un lugar óptimo para ponerla es lo más a la derecha posible, en pos+d\texttt{pos}+d.

Cuando se agota el alcance de la primera estación, podemos usar una lógica similar para colocar las siguientes dos: no hace falta que el alcance se extienda a la izquierda de la casa más a la izquierda sin cubrir, así que podemos colocar la siguiente estación lo más a la derecha posible otra vez.

Nuestra función de prueba devuelve verdadero si se pueden cubrir todas las casas colocando las estaciones de esta forma.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
const double EPSILON = 1e-7;
 
int main() {
	int n;
	cin >> n;
	vector<int> houses(n);
	for (int i = 0; i < n; i++) { cin >> houses[i]; }
	sort(houses.begin(), houses.end());
 
	auto possible_coords = [&](double d) -> pair<bool, array<double, 3>> {
		int used = 0;
		array<double, 3> pos = {houses[0] + d};
		// Chequea si cada casa está al alcance de la estación más reciente;
		// si no, construye una nueva (salvo que no queden)
		for (int i = 1; i < n; i++) {
			if (houses[i] - pos[used] > d) {
				used++;
				if (used == 3) { return {false, {}}; }
				pos[used] = houses[i] + d;
			}
		}
		return {true, pos};
	};
 
	double lo = 0, hi = 1e9;
	array<double, 3> ans;
 
	while (hi - lo > EPSILON) {
		double mid = (lo + hi) / 2;
		auto res = possible_coords(mid);
		if (res.first) {
			hi = mid;
			ans = res.second;
		} else {
			lo = mid;
		}
	}
 
	cout << fixed << lo << '\n';
	printf("%.6f %.6f %.6f\n", ans[0], ans[1], ans[2]);
}
import java.io.*;
import java.util.*;
 
public class ThreeBaseStations {
	private final static double EPSILON = 1E-7;
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int[] houses = new int[n];
		for (int i = 0; i < n; i++) { houses[i] = io.nextInt(); }
 
		Arrays.sort(houses);
		double lo = 0, hi = 1E9;
		double[] ans = new double[3];
 
		while (hi - lo > EPSILON) {
			double mid = (lo + hi) / 2;
			double[] res = possibleCoords(mid, houses);
			if (res.length != 0) {
				hi = mid;
				ans = res;
			} else {
				lo = mid;
			}
		}
 
		io.printf("%.6f\n", lo);
		io.printf("%.6f %.6f %.6f\n", ans[0], ans[1], ans[2]);
		io.close();
	}
 
	private static double[] possibleCoords(double d, int[] houses) {
		int used = 0;
		double[] pos = new double[3];
		pos[0] = houses[0] + d;
 
		// Chequea si cada casa está al alcance de la estación más reciente;
		// si no, construye una nueva (salvo que no queden)
		for (int i = 1; i < houses.length; i++) {
			if (houses[i] - pos[used] > d) {
				used++;
				if (used == 3) { return new double[0]; }
				pos[used] = houses[i] + d;
			}
		}
		return pos;
	}
 
	// CodeSnip{Kattio}
}
EPSILON = 1e-7
 
 
def possible_coords(d: int, houses: list) -> int:
	used = 0
	pos = [houses[0] + d] * 3
 
	# Chequea si cada casa está al alcance de la estación más reciente;
	# si no, construye una nueva (salvo que no queden)
	for i in range(1, len(houses)):
		if houses[i] - pos[used] > d:
			used += 1
			if used == 3:
				return None
			pos[used] = houses[i] + d
 
	return pos
 
 
n = int(input())
houses = list(map(int, input().split()))
houses.sort()
 
lo, hi = 0, 1e9
ans = [0.0] * 3
 
while hi - lo > EPSILON:
	mid = (lo + hi) / 2
	res = possible_coords(mid, houses)
 
	if res is not None:
		hi = mid
		ans = res
	else:
		lo = mid
 
print(f"{lo:.6f}")
print(f"{ans[0]:.6f} {ans[1]:.6f} {ans[2]:.6f}")
Fundamentos