The Meeting Place Cannot Be Changed

Explicación

Podemos hacer búsqueda binaria sobre el lugar donde se reunirán los amigos. Como queremos una precisión de $10^{-6}$ , paramos cuando la diferencia entre high y low es menor que $10^{-6}$ .

Cada vez que calculamos la respuesta, nos fijamos de qué lado vino la respuesta máxima. Si el máximo viene de ambos lados, no importa hacia dónde decidamos ir después: la respuesta solo aumentará, así que devolvemos esa respuesta. En cambio, si solo viene de un lado del punto que acabamos de calcular, movemos la búsqueda hacia ese lado, porque moverla hacia el otro lado solo aumentaría la respuesta.

Implementación

Complejidad temporal: $\mathcal{O}(N\log M)$ donde $M$ es la ubicación más al norte

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const double MAX_ERROR = 10e-7;
 
vector<double> locations;
vector<double> speeds;
 
double min_ans = (double)INT_MAX;
double curr_min_time;
bool left_has_max = false;  // de qué lado sale la respuesta máxima
bool right_has_max = false;
 
double get_time(double loc) {
	double max_time = 0;
	for (int i = 0; i < locations.size(); i++) {
		if (locations[i] == loc) { continue; }
		double i_time = abs(locations[i] - loc) / speeds[i];
		// tiempo que tarda el i-ésimo amigo en llegar a loc
		if (i_time > max_time) {
			left_has_max = false;  // reiniciamos a false, porque hay un nuevo máximo
			right_has_max = false;
			if (locations[i] > loc) {
				right_has_max = true;
			} else {
				left_has_max = true;
			}
			max_time = i_time;
		} else if (i_time == max_time) {
			// El máximo puede venir de ambos lados, así que no reiniciamos los 2 booleanos
			if (locations[i] > loc) {
				right_has_max = true;
			} else {
				left_has_max = true;
			}
		}
	}
	return max_time;
}
 
int main() {
	int n;
	cin >> n;
	locations.resize(n);
	speeds.resize(n);
 
	double low = 0;
	double high = 0;  // high será la ubicación del amigo más al norte
	double mid;
 
	for (int i = 0; i < n; i++) {
		cin >> locations[i];
		high = max(high, locations[i]);
	}
	for (int i = 0; i < n; i++) { cin >> speeds[i]; }
 
	while (high - low > MAX_ERROR) {
		mid = (high + low) / 2;
 
		// devuelve el tiempo que tardarían si los amigos se reunieran en mid
		curr_min_time = get_time(mid);
 
		min_ans = min(min_ans, curr_min_time);
		if (left_has_max && right_has_max) {
			break;
		} else if (left_has_max) {
			high = mid;
		} else {
			low = mid;
		}
	}
 
	cout << fixed << min_ans << endl;
}


import java.util.*;
 
public class MeetingPlace {
	static final double MAX_ERROR = 10e-7;
 
	static List<Double> locations = new ArrayList<>();
	static List<Double> speeds = new ArrayList<>();
 
	static double min_ans = Double.MAX_VALUE;
	static double curr_min_time;
	static boolean left_has_max = false;  // de qué lado sale la respuesta máxima
	static boolean right_has_max = false;
 
	/**
	 * Chequea si todos los amigos pueden converger en un punto en el intervalo
	 * de tiempo indicado.
	 */
	public static double get_time(double loc) {
		double max_time = 0;
		for (int i = 0; i < locations.size(); i++) {
			if (locations.get(i) == loc) { continue; }
			double i_time = Math.abs(locations.get(i) - loc) / speeds.get(i);
			if (i_time > max_time) {
				// reiniciamos a false, porque hay un nuevo máximo
				left_has_max = false;
				right_has_max = false;
				if (locations.get(i) > loc) {
					right_has_max = true;
				} else {
					left_has_max = true;
				}
				max_time = i_time;
			} else if (i_time == max_time) {
				// El máximo puede venir de ambos lados, así que no reiniciamos
				// los 2 booleanos
				if (locations.get(i) > loc) {
					right_has_max = true;
				} else {
					left_has_max = true;
				}
			}
		}
		return max_time;
	}
 
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		double low = 0;
		double high = 0;  // ubicación del amigo más al norte
 
		for (int i = 0; i < n; i++) {
			double location = scanner.nextDouble();
			locations.add(location);
			high = Math.max(high, location);
		}
 
		for (int i = 0; i < n; i++) { speeds.add(scanner.nextDouble()); }
 
		// Usamos búsqueda binaria para hallar el tiempo mínimo.
		while (high - low > MAX_ERROR) {
			double mid = (high + low) / 2;
			curr_min_time = get_time(mid);
			min_ans = Math.min(min_ans, curr_min_time);
			if (left_has_max && right_has_max) {
				break;
			} else if (left_has_max) {
				high = mid;
			} else {
				low = mid;
			}
		}
 
		System.out.printf("%.10f%n", min_ans);
	}
}


num_friends = int(input())
friend_coords = list(map(int, input().split()))
friend_veloci = list(map(int, input().split()))
 
 
def all_friends_converge(seconds: int) -> bool:
	"""
	Chequea si todos los amigos pueden converger en un punto en el intervalo de tiempo indicado.
 
	:param seconds: Cantidad de segundos dados para que los amigos converjan.
	:return: Si los amigos pueden converger a un solo punto.
	"""
 
	overlap_lower, overlap_upper = 1, 10**9
	for i in range(num_friends):
		lower_bound = friend_coords[i] - (friend_veloci[i] * seconds)
		upper_bound = friend_coords[i] + (friend_veloci[i] * seconds)
		if lower_bound > overlap_upper or upper_bound < overlap_lower:
			return False
		if lower_bound > overlap_lower:
			overlap_lower = lower_bound
		if upper_bound < overlap_upper:
			overlap_upper = upper_bound
	return True
 
 
left, right = 0, 10**9
diff = 10**-6
 
while left + diff < right:
	mid = (left + right) / 2
	last_comparison = all_friends_converge(mid)
	if last_comparison:
		right = mid
	else:
		left = mid + diff
 
# Hacemos la salida un poco más precisa
print(((left + mid) / 2) if last_comparison else ((mid + right) / 2))