Кластеры на карте эпицентров
Сейсмолог отметил на карте эпицентры землетрясений и хочет разбить их на группы так, как это делает DBSCAN: плотные скопления — кластеры, одинокие толчки — шум.
Даны n точек плоскости, радиус ε и порог minPts. Соседи точки — все точки на расстоянии не больше ε от неё, включая её саму (точки с одинаковыми координатами — разные точки и соседи друг друга). Точка — ядро, если у неё не меньше minPts соседей. Два ядра, которые соседи, лежат в одном кластере, и так по цепочке: кластер — это ядра, связанные цепочками соседей-ядер. Точка, которая не ядро, но соседствует хотя бы с одним ядром, — край. Все остальные точки — шум.
Выведите число кластеров, ядер, краёв и точек шума.
Тесты с третьего по пятый — настоящие эпицентры землетрясений магнитудой от 5 из каталога USGS: дуга островов на северо-западе Тихого океана за 2018–2021 годы и за все 2015–2025 годы, затем юго-запад Тихого океана за 2015–2025 годы. Координаты — километры на плоской карте области; расстояния от её середины на карте такие же, как по поверхности Земли.
Вход
В первой строке n, ε и minPts (1 ≤ n ≤ 10⁵, 0 ≤ ε ≤ 10⁶, 1 ≤ minPts ≤ n). Дальше n строк с целыми координатами x, y (по модулю не больше 10⁶). Гарантируется, что пар точек на расстоянии не больше ε — не больше 5·10⁵.
Выход
Четыре числа через пробел: кластеры, ядра, края, шум.
Примеры
Пример 1
9 2 3 0 0 1 1 2 0 1 -1 4 0 10 10 11 10 12 10 20 0
2 7 1 1
Пример 2
10 2 4 0 0 0 1 -1 0 -1 1 2 0 4 0 4 1 5 0 5 1 2 5
2 8 1 1
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 14 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сравнить каждую точку с каждой — 5·10⁹ расстояний на 10⁵ точках. Но соседей по условию немного: как не смотреть на точки, которые заведомо далеко?
2Подсказка 2
Разрежьте плоскость на квадраты со стороной ε. Где могут лежать соседи точки, если известен её квадрат?
3Подсказка 3
Ответ не зависит от того, в каком порядке обходить точки: ядра определяются числом соседей, кластеры — это связные группы ядер. Какая структура данных склеивает группы?
4Идея
Сосед точки отстоит от неё не больше чем на ε по каждой координате, значит, лежит в её квадрате сетки или в одном из восьми соседних. Разложим точки по квадратам в словарь и для каждой точки проверим только эти девять квадратов. Посчитав соседей, знаем ядра; кластеры — компоненты связности графа «ядро — соседнее ядро», их удобно собрать системой непересекающихся множеств (DSU). Край — не ядро, у которого среди соседей есть ядро.
5Разбор
Ключ квадрата — пара (⌊x/ε⌋, ⌊y/ε⌋). Округлять нужно именно вниз: в Python это //, а в Go оператор / округляет к нулю, и квадрат вокруг нуля получится вдвое шире остальных. Ответ от этого не испортится — соседи всё равно окажутся в соседних квадратах, — но точек на сравнение станет больше; честнее написать деление с округлением вниз.
Отдельный случай — ε = 0: делить на ноль нельзя, а соседи — это только точки с теми же координатами. Достаточно взять сторону квадрата max(ε, 1).
Удобно идти не по точкам, а по квадратам: для квадрата один раз собрать точки девяти квадратов вокруг и сравнить с ними каждую свою точку. Найденные списки соседей хранятся целиком — по условию их суммарная длина не больше n + 10⁶. Дальше три прохода: ядра (длина списка ≥ minPts), объединение каждого ядра с соседями-ядрами в DSU, затем подсчёт корней среди ядер и краёв среди остальных.
На первом настоящем тесте — 185 землетрясений 2018–2021 годов вдоль дуги островов на северо-западе Тихого океана при ε = 100 км и minPts = 4 — выходит 6 кластеров, 167 ядер, 6 краёв и 12 точек шума: те же числа, что в пошаговой сцене статьи.
5+Решение
6Сложность
O(n + C) времени, где C — число сравнений с точками девяти соседних квадратов. Когда точки распределены без вырожденных скоплений, C — небольшое кратное числу пар соседей. Памяти O(n + число пар соседей).
Заметьте: сетка не делает задачу линейной в худшем случае. Если все точки лежат в двух соседних квадратах, но дальше ε друг от друга, сравнений снова около n². В тестах таких скоплений нет; общий случай — в статье, в разделе о сложности.
7Типичные ошибки
- Перебор всех пар. Ответ верный, но на 10⁵ точках — превышение времени.
- Не считать саму точку. По условию точка — свой собственный сосед; без неё ядер меньше, и ответ расходится почти во всех тестах.
- Склеивать кластеры через края. Если объединять ядро со всеми соседями, а не только с ядрами, край между двумя кластерами сольёт их в один. Это ловит второй пример: две группы по четыре ядра и одна точка посередине.
- Деление на ноль при ε = 0 — сторона квадрата должна быть хотя бы 1.
- Край, посчитанный дважды, если он соседствует с ядрами двух кластеров. Края считаются по точкам, а не по парам «край — кластер».