Задача №3398. Велогонка
Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на \(x_1\), \(x_2\), ..., \(x_n\) метров (\(n\) – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью \(v_1\), \(v_2\), ..., \(v_n\) метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.
Репортёр, освещающий ход соревнований, хочет определить момент времени, в который расстояние между лидирующим в гонке велосипедистом и замыкающим гонку велосипедистом станет минимальным, чтобы с вертолёта сфотографировать сразу всех участников велогонки.
Требуется написать программу, которая по заданному количеству велосипедистов \(n\), заданным начальным положениям велосипедистов \(x_1\), \(x_2\), ..., \(x_n\) и их скоростям \(v_1\), \(v_2\), ..., \(v_n\), вычислит момент времени \(t\), в который расстояние \(l\) между лидирующим и замыкающим велосипедистом будет минимальным.
Первая строка входного файла содержит целое число \(n\) – количество велосипедистов.
В последующих n строках указаны по два целых числа: \(x_i\) – расстояние от старта до \(i\)-го велосипедиста в начальный момент времени (\(0 \leq x_i \leq 10^7\)) и \(v_i\) – его скорость (\(0 \leq v_i \leq 10^7\)).
В выходной файл необходимо вывести два вещественных числа: \(t\) – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, \(l\) – искомое расстояние.
Числа t и l должны иметь абсолютную или относительную погрешность не более \(10^{–6}\), что означает следующее. Пусть выведенное число равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет считаться правильным, если значение выражения \(|x – y| / max(1, |y|)\) не превышает \(10^{–6}\).
Данная задача содержит четыре подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(2 \leq n \leq 50\), \(0 \leq x_i \leq 1000\), \(0 \leq v_i \leq 1000\). Гарантируется, что существует ответ, в котором \(t\) – целое число, не превышающее 1000.
\(2 \leq n \leq 200\).
\(2 \leq n \leq 2000\)
\(2 \leq n \leq 10^5\)
3 0 40 30 10 40 30
1 30
5 90 100 100 70 100 70 110 60 120 35
0.5 5.000000000000