Весь отрыв в кадре
Фотограф на мотоцикле едет рядом с отрывом велогонки и хочет снять всех гонщиков отрыва одним кадром. Чем плотнее группа, тем лучше снимок. Гонщики едут по прямому шоссе, каждый со своей постоянной скоростью; одни догоняют других, и лидер группы и замыкающий за время съёмки могут смениться не раз. Снимать можно с момента 0 до момента T. Найдите, насколько растянута группа в самый плотный момент: наименьшее за [0, T] расстояние от первого гонщика до последнего.
Гонщик i в момент t находится в точке xi + vi·t. Обгоны не мешают никому: шоссе широкое, все едут с прежней скоростью.
Вход
В первой строке число гонщиков n и длительность съёмки T в секундах (1 ≤ n ≤ 105, 1 ≤ T ≤ 104, T целое). Дальше n строк xi vi: положение гонщика в момент 0 в метрах — целое от 0 до 105 — и его скорость в м/с от 5 до 25, не больше чем с двумя знаками после запятой.
Выход
Наименьшая длина группы в метрах. Ответ принимается, если его ошибка не больше 10−6 — абсолютная для ответов меньше единицы, относительная для остальных.
Примеры
Пример 1
3 100 0 12.00 100 10.00 40 11.00
10.000000
Пример 2
2 30 0 13.00 400 8.00
250.000000
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Длина группы в момент t — это L(t) = maxi(xi + vit) − mini(xi + vit). Лидер и замыкающий меняются, и кажется, что у такой функции может быть сколько угодно ям. Нарисуйте её для первого примера. Что можно сказать о функции «наибольшая из нескольких прямых»?
2Подсказка 2
Наибольшая из прямых — выпуклая ломаная: каждая прямая выпукла, а максимум выпуклых функций выпуклый. Наименьшая из прямых — вогнутая. А их разность?
3Идея
L(t) = maxi(xi + vit) + maxi(−xi − vit) — сумма двух выпуклых функций, значит, выпуклая. У выпуклой функции на отрезке нет ложных ям: она убывает до минимума, может постоять на площадке, а потом растёт. Поэтому минимум находит поиск из статьи о троичном поиске, а вычислить L(t) в одной точке — один проход по гонщикам.
4Разбор
Почему разность — выпуклая. Функция выпукла, если отрезок между двумя точками её графика лежит не ниже графика. Для прямой это равенство. Если каждая из функций fi выпукла, то max fi(λa + (1 − λ)b) ≤ max (λfi(a) + (1 − λ)fi(b)) ≤ λ max fi(a) + (1 − λ) max fi(b) — максимум тоже выпуклый. Минус наименьшей из прямых — это наибольшая из прямых −xi − vit, и сумма двух выпуклых выпукла.
Теорема статьи требует строгой унимодальности, а у L бывают площадки — в последнем тесте целых 400 секунд. Для выпуклой функции это не страшно. Если L(m₁) > L(m₂) при m₁ < m₂, то на [0, m₁] значения не меньше L(m₁): иначе точка m₁ лежала бы выше отрезка, соединяющего две другие точки графика. Значит, кусок левее m₁ можно выбросить, не потеряв минимума. Если значения равны, хотя бы одна точка минимума лежит на [m₁, m₂] — по тому же рассуждению с обеих сторон, — и подойдёт любой из двух кусков. Площадки у выпуклой функции бывают только на самом дне, где они безвредны.
Золотое сечение на [0, T] до ширины 10−8 секунды. Длина группы меняется не быстрее чем на 20 м в секунду — это наибольшая разница скоростей, — поэтому ошибка ответа не больше 2·10−7 м. В конце стоит сравнить и концы отрезка: минимум бывает в момент 0 или в момент T, как во втором примере.
Точный способ тоже есть: построить верхнюю огибающую прямых и нижнюю, как в трюке выпуклой оболочки, и проверить все их изломы — минимум выпуклой ломаной лежит в изломе или на конце. Это O(n log n), но кода втрое больше.
4+Решение
5Сложность
Около 60 вычислений L по O(n) каждое — 6·106 простых действий. Троичный поиск — вдвое больше, тоже успевает.
6Типичные ошибки
- Крайние гонщики не меняются. Взять лидера и замыкающего в момент 0 и следить только за ними — это
wrong.py. В первом примере он отвечает 0: лидер и замыкающий поравняются на 50-й секунде, но к этому моменту замыкающим уже стал третий гонщик, и группа растянута на 10 метров. - Все пары гонщиков. Минимум лежит в момент, когда сравнялись какие-то двое, но пар — 5·109, и для каждой ещё нужен проход по всем.
- Сетка по целым секундам. Минимум бывает и между секундами, а ломаная у дна — острый угол: ошибка в полсекунды стоит метров.
- Остановка по относительной ширине. Если остановить поиск, когда отрезок сжался до 10−9·T, при T = 104 это 10−5 секунды, и при разнице скоростей в 20 м/с ошибка доходит до 2·10−4 м — больше допуска, когда группа почти сходится в точку, как в восьмом тесте.