CS
Задачник Базовый курс EN

Задача

Самый дальний бросок

поиск оптимизация точность вычислений наука и физика

Тренер моделирует броски на компьютере: ядро, теннисный мяч, волан из перьев. Для каждого снаряда известны скорость выпуска, высота выпуска и то, как сильно его тормозит воздух. Нужно узнать, как далеко можно забросить снаряд, если выбрать лучший угол. Формулы для дальности с сопротивлением воздуха нет, и каждый бросок моделируют шаг за шагом — это дорого, и угол нужно найти за небольшое число полётов.

Полёт под углом θ градусов к горизонту при скорости v, высоте выпуска h и установившейся скорости падения vt считается так — ровно как в листинге статьи. Пусть g = 9,81, шаг d = 0,002 с, k = g / vt2, а при vt = 0 (бросок в пустоте) k = 0. Ускорение при скорости (vx, vy) равно a(vx, vy) = (−k·s·vx, −g − k·s·vy), где s = √(vx2 + vy2). В начале x = 0, y = h, vx = v·cos θ, vy = v·sin θ. Шаг метода Рунге — Кутты:

  • a1 = a(v), v2 = v + a1·d/2, a2 = a(v2), v3 = v + a2·d/2, a3 = a(v3), v4 = v + a3·d, a4 = a(v4) — для каждой координаты отдельно;
  • новое положение: x′ = x + d·(vx + 2v2x + 2v3x + v4x)/6, так же y′;
  • если y′ < 0, снаряд упал, и дальность равна x + (x′ − x)·y / (y − y′);
  • иначе новая скорость: vx += d·(a1x + 2a2x + 2a3x + a4x)/6, так же vy, и положение становится (x′, y′).

Дальность как функция угла на отрезке [0°, 90°] строго растёт до вершины и строго убывает после неё. Одна оговорка: при h = 0 и совсем малых углах снаряд уходит под землю уже на первом шаге, и дальность равна нулю — на этом коротком куске у функции площадка. Один полёт — до четырёх тысяч шагов.

Вход

В первой строке число снарядов q (1 ≤ q ≤ 20). Дальше q строк v h vt: скорость выпуска в м/с (1 ≤ v ≤ 50), высота выпуска в метрах (0 ≤ h ≤ 3) и установившаяся скорость падения в м/с (vt = 0 или 1 ≤ vt ≤ 200). Числа даны не больше чем с двумя знаками после запятой.

Выход

q строк: наибольшая дальность каждого снаряда в метрах. Ответ принимается, если его относительная ошибка не больше 10−6 (для дальностей меньше метра — абсолютная).

Примеры

Пример 1

Вход
4
13.5 2.1 0
13.5 2.1 149
30 1 21.1
50 1 6.8
Выход
20.571066
20.443074
40.927930
12.489273

Пример 2

Вход
2
10 0 0
10 0 10
Выход
10.193678
6.051037

Ограничения

Время · Python
10000 мс
Время · Go
2000 мс
Память
256 МБ
Проверка
8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Перебрать углы с шагом в сотую градуса — девять тысяч полётов на снаряд, по нескольку тысяч шагов в каждом. Перебор по целым градусам быстр, но вершина лежит между ними. Насколько точно нужен угол, чтобы дальность сошлась до миллионной доли?

2Подсказка 2

Про функцию известно главное: до вершины она растёт, после — убывает. Что можно сказать о вершине, если сравнить дальности под двумя углами?

3Идея

Это поиск вершины унимодальной функции из статьи. Две точки внутри отрезка: если дальше летит снаряд, брошенный под бо́льшим углом, вершина правее меньшего угла, иначе — левее бо́льшего. Каждый шаг выбрасывает часть отрезка, и до нужной точности хватает нескольких десятков полётов. Золотое сечение тратит на шаг один полёт, а не два: одна из точек переходит в следующий шаг вместе со своей дальностью.

4Разбор

Полёт пишется ровно по условию — порядок действий тот же, что в листинге статьи, и результат совпадёт до последних знаков. Поиск — на отрезке [0°, 90°] до ширины 10−3 градуса, ответ — наибольшая из дальностей, посчитанных в последних точках.

Почему такой точности хватает. Около вершины дальность ведёт себя как R − c·δ2, где δ — отклонение угла в радианах, а c — порядка удвоенной дальности: у броска в пустоте с земли R(θ) = v2 sin 2θ / g, и при отклонении на δ от 45° дальность падает в cos 2δ ≈ 1 − 2δ2 раза. При δ ≈ 10−5 радиана — а тысячная градуса меньше двух стотысячных радиана — относительная ошибка порядка 10−9, с огромным запасом. Это и есть корень из точности, о котором говорит статья: дальность сходится вдвое быстрее угла.

Площадка при h = 0 поиску не мешает: она у самого нуля, где дальность наименьшая, а точки поиска с первого шага стоят около 34° и 56° и к нулю приближаются, только если вершина там.

4+Решение
5Сложность

Золотое сечение — 26 полётов на снаряд, троичный поиск — около шестидесяти, по O(T/d) шагов на полёт, где T — время полёта. Самый тяжёлый тест эталон на Python проходит примерно за секунду.

6Типичные ошибки
  • Целые градусы. 91 полёт на снаряд, быстро, но лучший целый угол отстоит от настоящего до полуградуса, и дальность теряет миллиметры — больше допустимой ошибки. Это wrong.py, он ошибается уже на первом примере.
  • Мелкая сетка. Шаг в четверть градуса уже почти точен, но это 361 полёт на снаряд, и Python не укладывается во время. Чтобы попасть в допуск сеткой наверняка, нужен шаг меньше десятой градуса — тысяча полётов.
  • Формула для пустоты. tg θ = v / √(v2 + 2gh) верна только без воздуха. Теннисный мяч из статьи лучше бросать под 38°, а не под 44,7°, как велит формула, а волан — под 24°.
  • Другой шаг полёта. Шаг 0,01 с вместо 0,002 сдвигает дальность теннисного мяча на 0,06 мм — этого уже хватает, чтобы выйти за допуск, а метод Эйлера вместо Рунге — Кутты — на 7 мм.

Алгоритмы задачи

SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи
Каталог алгоритмов