Велогонка
Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на $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