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

Задача

Упростить тропу

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

Приложение для походов хранит тропы упрощёнными: из трека оставляют только точки, без которых форма тропы искажается больше чем на допуск ε метров. Упрощают алгоритмом Рамера — Дугласа — Пекера, и чтобы на всех устройствах результат был одинаковым, правила записаны точно.

  • Первая и последняя точки остаются всегда.
  • Для пары оставленных точек i < j, между которыми есть другие, находим самую далёкую от отрезка PiPj точку: расстояние — до ближайшей точки отрезка (если Pi = Pj, то просто до этой точки). Из нескольких одинаково далёких берём точку с меньшим номером.
  • Если её расстояние строго больше ε, она остаётся, и правило применяется к парам (i, k) и (k, j). Иначе все точки между i и j выбрасываются.

Выведите, какие точки останутся. Тесты с третьего по шестой и девятый — горные тропы к югу от Алматы из OpenStreetMap в целых метрах; девятый — маршрут «туда и обратно», который кончается там же, где начался.

Вход

В первой строке число точек n (2 ≤ n ≤ 20 000) и допуск ε (0 ≤ ε ≤ 10⁴). Дальше n строк с координатами точек трека x y по порядку. Все числа целые, |x|, |y| ≤ 10⁴. Точки могут повторяться, в том числе подряд.

Выход

В первой строке — сколько точек осталось, во второй — их номера (с единицы) по возрастанию, через пробел.

Примеры

Пример 1

Вход
13 1
0 0
6 1
12 1
13 3
7 4
1 5
2 7
8 8
14 8
15 10
17 15
20 16
24 21
Выход
9
1 3 4 6 7 9 11 12 13

Пример 2

Вход
7 2
0 0
4 1
8 0
14 1
30 2
20 1
10 0
Выход
3
1 5 7

Ограничения

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

Разбор

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

1Подсказка 1

Алгоритм из статьи подходит дословно — вопрос в точности. Расстояния — корни, и сравнивать их в числах с плавающей точкой значит рисковать, что одинаково далёкие точки окажутся «чуть-чуть» разными. Можно ли сравнивать расстояния, не извлекая корней и не деля?

2Подсказка 2

У всех точек между i и j один и тот же отрезок. Умножьте квадраты их расстояний на одно и то же число L = |Pj − Pi|² — у всех получатся целые числа. Чему равен квадрат расстояния до прямой, умноженный на L?

3Идея

Пусть d = Pj − Pi, p = Pm − Pi. Скалярное произведение p · d говорит, куда падает перпендикуляр: меньше нуля — за начало отрезка, больше L — за конец, иначе на отрезок. В первых двух случаях расстояние — до конца отрезка, и d²·L — целое. В третьем расстояние до прямой равно |p × d| / √L, и d²·L = (p × d)². Сравниваем эти целые числа между собой, а с допуском — число ε²·L.

4Разбор

Стек пар (i, j), сначала (1, n). Для пары считаем vm = d²(m)·L для всех m между ними по правилам выше и берём первый максимум. Если он больше ε²·L, отмечаем точку и кладём в стек обе половины. Если L = 0 — начало и конец совпадают, как у маршрута «туда и обратно», — расстояние считаем до этой точки, а множитель берём равным единице.

Стек вместо рекурсии — не прихоть: в восьмом тесте каждое деление отщипывает по одной точке, глубина рекурсии дошла бы до тысячи, а это предел Python по умолчанию.

Числа не переполняются: координаты до 10⁴, разности до 2·10⁴, квадрат длины до 8·10⁸, произведения — до 6,4·10¹⁷ при пределе int64 около 9,2·10¹⁸.

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

Каждая пара — проход по точкам между её концами. Если самая далёкая точка делит кусок примерно пополам, всего O(n log n); в худшем случае, как в восьмом тесте, O(n²) — для тысячи точек это полмиллиона расстояний.

6Типичные ошибки
  • Расстояние до прямой, а не до отрезка. Так написано во многих учебных версиях алгоритма, и это неверное решение задачи. Точка далеко за концом хорды, но рядом с её продолжением, кажется близкой и пропадает. Во втором примере тропа ведёт к смотровой площадке и возвращается — и смотровая исчезает. На настоящих тропах из тестов эта ошибка случайно не проявляется: их хорды не заходят за концы так далеко.
  • Числа с плавающей точкой. Корни и деления дают расстояния, которые у равноудалённых точек могут различаться в последнем знаке, и «первый максимум» становится лотереей.
  • Нестрогое сравнение. Точка на расстоянии ровно ε выбрасывается: условие — «строго больше». В тесте с нулевым допуском это решает, остаются ли точки, лежащие точно на хорде.

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

GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи
Каталог алгоритмов