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

Задача

Порог плотности

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

Перед тем как запускать DBSCAN, нужно выбрать радиус ε. Аналитик хочет крутить его вперёд и назад и сразу видеть, сколько точек при этом радиусе будут ядрами. А иногда спрашивает наоборот: при каком наименьшем радиусе ядрами станут хотя бы c точек — например, четыре точки из пяти.

Даны n точек плоскости и порог minPts. При радиусе ε соседи точки — все точки на расстоянии не больше ε от неё, включая её саму (точки с одинаковыми координатами — разные точки). Точка — ядро, если соседей не меньше minPts. Ответьте на запросы двух видов:

  • 1 e — сколько ядер при ε = e;
  • 2 c — наименьшее целое ε, при котором ядер не меньше c.

Тесты с третьего по пятый — настоящие эпицентры землетрясений магнитудой от 5 из каталога USGS: дуга островов на северо-западе Тихого океана за 2018–2021 годы и за все 2015–2025 годы, затем юго-запад Тихого океана за 2015–2018 годы. Координаты — километры на плоской карте области.

Вход

В первой строке n и minPts (1 ≤ minPts ≤ n ≤ 2000). Дальше n строк с целыми координатами x, y (по модулю не больше 10⁶). Затем число запросов q (1 ≤ q ≤ 10⁵) и q строк с запросами: в запросе первого вида 0 ≤ e ≤ 3·10⁶, второго — 1 ≤ c ≤ n.

Выход

На каждый запрос — число в отдельной строке.

Примеры

Пример 1

Вход
6 3
0 0
3 4
6 8
0 10
20 0
20 1
6
1 4
1 5
1 10
2 1
2 3
2 6
Выход
0
1
4
5
7
17

Пример 2

Вход
4 3
2 2
2 2
2 2
7 2
5
1 0
1 4
1 5
2 4
2 3
Выход
3
3
4
5
0

Ограничения

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

Разбор

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

1Подсказка 1

Пересчитывать соседей заново на каждый запрос — до 10⁵ раз по 4·10⁶ расстояний. Что про отдельную точку меняется, когда ε растёт?

2Подсказка 2

Если точка — ядро при каком-то ε, она ядро и при любом большем. Значит, у каждой точки есть свой порог: с какого ε она становится ядром. Чему он равен?

3Подсказка 3

Ядру нужны minPts соседей, и одна из них — сама точка. Сколько других точек должно попасть в круг?

4Идея

Порог точки — расстояние до её (minPts − 1)-го ближайшего соседа среди остальных точек (при minPts = 1 — ноль). Это и есть «расстояние ядра», из которого строится отсортированный график для выбора ε в статье. Посчитаем порог для каждой точки и отсортируем: число ядер при ε — это сколько порогов не больше ε (двоичный поиск), а наименьший ε для c ядер — c-й по величине порог.

5Разбор

Для каждой точки посчитаем квадраты расстояний до всех точек, включая её саму, и отсортируем: на позиции 0 окажется сама точка (или её двойник — тоже 0), а на позиции minPts − 1 — нужный порог. Работать удобно с квадратами расстояний: всё остаётся в целых числах, и сравнение «порог ≤ ε» превращается в «квадрат порога ≤ ε²».

Запрос первого вида — bisect_right по отсортированным квадратам порогов со значением e². Во втором виде нужен c-й по величине квадрат порога D, а ответ — наименьшее целое ε с ε² ≥ D: это ⌈√D⌉. Точнее всего взять целый корень (math.isqrt) и прибавить единицу, если он не точный. В Go целого корня в стандартной библиотеке нет: можно взять math.Sqrt и поправить результат в целых, пока r² не окажется ровно на месте.

На дуге островов за одиннадцать лет (913 землетрясений, minPts = 10) при ε = 100 км ядрами оказываются 854 точки, а чтобы ядрами стали 80 % — 731 точка, — хватает 58 км. За одиннадцать лет толчков в каждом месте дуги накопилось много, и порог плотности проходится уже на малом радиусе.

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

O(n² log n) на пороги (сортировка расстояний для каждой точки; можно и O(n²) выбором k-го элемента) и O(n log n + q log n) на сортировку порогов и ответы. Для больших n пороги считают через сетку или k-d дерево: нужны только minPts − 1 ближайших соседей, а не все расстояния.

7Типичные ошибки
  • Сосед на один дальше. Если взять расстояние до minPts-го другого соседа, забыв, что точка считает себя, каждый порог окажется на одного соседа строже. Так читают график k-расстояний в исходной статье буквально — с k = minPts; поправку «k = minPts − 1» позже явно оговаривают Шуберт и соавторы. Ловится уже первым примером.
  • Пересчёт на каждый запрос. Верно, но 10⁵ запросов по 4·10⁶ расстояний не уложатся ни в какое время.
  • Строго меньше вместо «не больше». Точка ровно на расстоянии ε — сосед, поэтому порог, равный ε, проходит: нужен bisect_right, а не bisect_left. В первом примере при ε = 5 порог точки (3, 4) равен ровно 5.

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

ML Алгоритм DBSCAN Собирает в кластеры плотные области точек любой формы, а одинокие точки помечает как шум. O(n·Q + Σ|N(p)|) 2 задачи SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи
Каталог алгоритмов