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

Задача

Навигатор без тригонометрии

точки на плоскости карты и навигация геоданные точность вычислений

Маршрут — ломаная из n точек P1, …, Pn. В каждой внутренней точке Pi направление меняется: въезжаем по вектору u = Pi − Pi−1, выезжаем по вектору w = Pi+1 − Pi. Пусть θ — угол поворота от u к w, от −180° до 180°. Навигатор говорит:

  • ничего, если |θ| ≤ 45°;
  • left или right, если 45° < |θ| < 135°;
  • sharp left или sharp right, если 135° ≤ |θ| < 180°;
  • u-turn, если |θ| = 180°: дорога развернулась ровно назад.

Налево — против часовой стрелки, ось y направлена вверх. Границы точные: поворот ровно на 45° — ещё «прямо», ровно на 135° — уже «круто». Координаты бывают до миллиарда, и ответ должен быть верным даже для поворота, который отличается от 45° на миллиардную долю градуса.

Второй и третий тесты — маршруты курьера по улицам Алматы из OpenStreetMap, координаты в дециметрах.

Вход

В первой строке n (2 ≤ n ≤ 30 000), дальше n строк с целыми координатами x, y (|x|, |y| ≤ 10⁹). Соседние точки различны.

Выход

В первой строке число подсказок k. Дальше k строк в порядке маршрута: номер точки (точки нумеруются с единицы) и подсказка.

Примеры

Пример 1

Вход
8
0 0
4 0
8 4
4 8
4 2
4 9
10 9
16 10
Выход
4
3 left
4 sharp left
5 u-turn
6 right

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
9 тестов

Разбор

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

1Подсказка 1

Угол здесь не нужен. Сравните, что говорят о θ векторное и скалярное произведение, и выразите условие «|θ| ≤ 45°» через них, без синусов и арктангенсов.

2Идея

Векторное произведение c = u × w = |u||w| sin θ, скалярное d = u · w = |u||w| cos θ. Множитель |u||w| положительный и одинаковый, поэтому сравнивать можно сами c и d, как если бы это были синус и косинус.

  • |θ| ≤ 45° ⇔ cos θ ≥ |sin θ| ⇔ d > 0 и |c| ≤ d.
  • |θ| ≥ 135° ⇔ −cos θ ≥ |sin θ| ⇔ d < 0 и |c| ≤ −d.
  • |θ| = 180° ⇔ c = 0 и d < 0.
  • Сторону поворота даёт знак c.

Все величины — целые числа, сравнения точные, и граница в 45° проходит ровно там, где сказано в условии.

3Разбор

Проверяем в порядке: сначала разворот, потом «прямо», потом «круто», иначе обычный поворот. Порядок важен: разворот тоже подходит под условие «|c| ≤ −d», но подсказка у него своя.

Почему не atan2? Он почти всегда даёт верный ответ, но пятый тест собран из поворотов, которые отличаются от 45° и 135° на ничтожную величину: |c| и d различаются на единицу при значениях около 10¹⁷. Число double хранит 15–16 значащих цифр, и при переводе в него эта единица теряется. Такие пары векторов легко построить: нужно решить в целых числах уравнение |c| − d = ±1, а это линейное уравнение относительно координат w, и его решает расширенный алгоритм Евклида. Так генератор тестов и устроен.

Переполнения нет: разности координат до 2·10⁹, произведения до 4·10¹⁸, c и d до 8·10¹⁸ — в int64 помещаются. Модуль |c| тоже безопасен: −8·10¹⁸ меняет знак без переполнения.

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

O(n): по несколько умножений на каждую точку.

5Типичные ошибки
  • Угол через atan2 или arccos. Проходит все тесты, кроме пятого, где повороты стоят на самой границе.
  • «<» вместо «≤». Поворот ровно на 45° — «прямо». В примере это вторая точка маршрута.
  • Разворот как «sharp». При θ = 180° векторное произведение равно нулю, и знак стороны не определён; это отдельная подсказка.
  • Нормировка векторов. Деление на длины даёт дроби и корни, а для сравнения они не нужны: общий положительный множитель на знаки и сравнения не влияет.

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

GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи
Каталог алгоритмов