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

Карта на всех масштабах

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

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

Правила упрощения те же, что в задаче «Упростить тропу»: концы каждой тропы остаются; для пары оставленных точек ищется самая далёкая от отрезка между ними точка (из равноудалённых — с меньшим номером); она остаётся и делит пару на две, если её расстояние строго больше ε, иначе все точки между концами пары выбрасываются. Каждая тропа упрощается отдельно.

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

Вход

В первой строке число троп T (T ≥ 1). Каждая тропа — число точек n (n ≥ 2) и n строк с координатами x y по порядку. Всего точек во всех тропах не больше 100 000; все координаты целые, |x|, |y| ≤ 16 000; точки могут повторяться. Затем число запросов q (1 ≤ q ≤ 100 000) и строка из q целых допусков ε (0 ≤ ε ≤ 10⁵).

Выход

Для каждого допуска в отдельной строке — сколько точек всех троп останется после упрощения с этим допуском.

Примеры

Пример 1

Вход

2
13
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
7
0 0
4 1
8 0
14 1
30 2
20 1
10 0
13
0 1 2 3 4 5 6 7 8 9 10 11 12

Выход

Ограничения

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

Разбор

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

1Подсказка 1

Запустить упрощение заново для каждого допуска — это сотня тысяч проходов по сотне тысяч точек. Что в работе алгоритма не зависит от ε?

2Подсказка 2

Самая далёкая от отрезка точка не зависит от допуска. Значит, при любом ε алгоритм делит тропу по одному и тому же дереву, а ε решает только, где деление остановится. Когда точка выживает при допуске ε?

3Идея

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

4Разбор

Расстояния сравниваем в целых числах, как в задаче «Упростить тропу»: для пары с L = |P_j − P_i|² у каждой точки между ними считаем v = d²·L (если L = 0, просто d²). Самая далёкая точка — первый максимум v. Её собственный целый порог — наибольшее e с d > e, то есть с e²·L < v: это e = ⌊√((v − 1) / L)⌋, корень целочисленный. Порог точки — min(e, порог родителя); в стек кладём обе половины вместе с этим числом. Точки с v = 0 лежат на отрезке и не выживают ни при каком ε ≥ 0 — их пары дальше не делим.

Все пороги складываем в один массив и сортируем. Ответ на ε — 2·T + (число порогов ≥ ε), его даёт двоичный поиск.

Числа: при координатах до 16 000 квадрат расстояния до 2·32 000² ≈ 2·10⁹, а v — до 4,2·10¹⁸. Это ещё помещается в int64.

4+Решение

5Сложность

Один проход упрощения — O(N log N) на типичных тропах и O(N²) в худшем случае, сортировка порогов — O(N log N), каждый запрос — O(log N).

6Типичные ошибки

Порог — собственное расстояние точки. Кажется, что потомки в дереве ближе к своим отрезкам, чем предки, но это не так. В примере у серпантина точка 6 отстоит от своего отрезка на 11,70, а её родитель, точка 3, — на 7,15; при допуске 8 родитель выпадает, и точка 6 вместе с ним. Это неверное решение задачи; на настоящих тропах из второго теста оно ошибается на большинстве запросов.
Упрощение заново на каждый запрос. Верно, но сто тысяч проходов по сотне тысяч точек не уложатся ни в какое время.
Пороги в числах с плавающей точкой. Сравнивать ε с вещественным расстоянием можно, но на точках, где расстояние — ровно целое число (в целочисленных координатах так бывает), ошибка в последнем знаке переворачивает ответ.

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

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