Время круга
Траектория машины на кольцевой трассе — замкнутая ломаная из n точек P1, …, Pn, перечисленных по ходу движения; после Pn снова идёт P1. Машину ограничивают три правила.
- Повороты. Скорость в точке Pi не больше √(a·Ri), где Ri — радиус окружности через Pi−1, Pi, Pi+1, и не больше V. Если три точки лежат на одной прямой, ограничение только V.
- Разгон. Если di — длина отрезка от Pi до Pi+1, а vi — скорость в Pi, то vi+12 ≤ vi2 + 2b·di.
- Торможение. vi2 ≤ vi+12 + 2c·di.
Машина едет круг за кругом, и в каждой точке скорость — наибольшая, какую позволяют все три правила (такой набор скоростей единственный). Отрезок от Pi до Pi+1 она проходит за 2di / (vi + vi+1) секунд. Сколько длится круг?
Вход
В первой строке n, a, b, c, V (3 ≤ n ≤ 200 000; a, b, c — ускорения в м/с², от 0,1 до 100; V — наибольшая скорость в м/с, от 1 до 1000; числа могут быть дробными). Дальше n строк с координатами точек в метрах, по модулю не больше 105. Соседние точки не совпадают.
Выход
Время круга в секундах. Ответ засчитывается, если его относительная погрешность не больше 10−6.
Примеры
Пример 1
4 10 5 10 100 0 0 100 0 100 50 0 50
12.688455161
Пример 2
14 12 4 9 60 0 0 50 0 100 0 150 0 200 0 220 20 220 40 200 60 150 60 100 60 50 60 0 60 -20 40 -20 20
19.362116936
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сначала посчитайте для каждой точки «потолок» по повороту: радиус окружности через три точки равен произведению длин трёх сторон треугольника, делённому на учетверённую его площадь, то есть на 2·|векторное произведение|. Если бы не было правил разгона и торможения, ответ был бы суммой времён отрезков с этими скоростями. Что меняют два других правила?
2Подсказка 2
Если пройти по кругу вперёд, ограничивая скорость разгоном, а потом назад, ограничивая торможением, получится почти ответ. Но с какой точки начинать, если круг замкнут и скорость в начале неизвестна? Есть одна точка, скорость в которой известна наверняка.
3Идея
Набор скоростей, который удовлетворяет всем правилам, назовём допустимым. Если два набора допустимы, то и их поточечный максимум допустим: например, max(ui+1, wi+1)2 ≤ max(ui2, wi2) + 2b·di. Поэтому наибольший допустимый набор существует и единственный — это и есть скорости машины.
Пусть s — точка с самым низким потолком Ls. Набор «везде скорость Ls» допустим: он не выше ни одного потолка, а разгон и торможение при постоянной скорости ничего не требуют. Значит, в наибольшем наборе скорость в каждой точке не меньше Ls, а в самой s — ровно Ls. Это точка, где скорость известна.
Дальше два прохода от s. Вперёд: vi = min(Li, √(vi−12 + 2b·di−1)). Назад: vi = min(vi, √(vi+12 + 2c·di)). Любой допустимый набор не выше результата: это проверяется индукцией вдоль каждого прохода, начиная с s, где допустимая скорость не больше Ls. А сам результат допустим: обратный проход понижает скорость только там, где впереди скорость ниже, и правило разгона там выполняется само собой; на стыке в точке s ничего не ломается, потому что все скорости не ниже Ls.
4Разбор
Посчитать длины отрезков и потолки, найти точку с наименьшим потолком, сделать по кругу проход вперёд и проход назад, сложить времена 2di / (vi + vi+1). Если три точки на одной прямой, векторное произведение равно нулю, и потолок — просто V.
Шестой и седьмой тесты — кольцо автодрома «Сокол» и машина из статьи: по оси дороги круг длится 100,363 секунды, по траектории, которую нашёл генетический алгоритм листинга, — 100,352. Именно эту функцию генетический алгоритм вызывает тысячи раз.
4+Решение
5Сложность
O(n): два прохода по кругу и один по отрезкам.
6Типичные ошибки
- Начать с первой точки. Скорость в ней заранее неизвестна: если за ней тесный поворот, а перед ней — конец прямой, проходы, начатые с неё, не учитывают торможение через стык круга. Пятый и восьмой тесты построены так, что медленный поворот приходится как раз на стык.
- Только проход вперёд. Тогда машина влетает в поворот на полной скорости и тормозит мгновенно; круг получается короче настоящего.
- Деление на ноль на прямых участках, где три точки на одной линии.
- Разные пары соседних точек. В правиле разгона di — отрезок до точки i + 1, а при проходе вперёд к точке i нужен отрезок от i − 1; перепутать индекс легко, и на неравномерной ломаной это меняет ответ.