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

Задача

Мосты и тоннели

пересечения карты и навигация геоданные хеширование олимпиады

В OpenStreetMap улицы, которые пересекаются на одном уровне, обязаны иметь общий узел — перекрёсток. Если общего узла нет, одна улица проходит над другой, и у неё должен быть другой слой: мост выше, тоннель ниже. Проверяющая программа получает улицы, разрезанные на отрезки, и считает места, где внутренности двух отрезков пересекаются в одной точке. Если у отрезков разные слои — это мост или тоннель; если слой один — ошибка в данных.

Касания не считаются: конец отрезка на другом отрезке — это перекрёсток или примыкание, а отрезки на одной прямой с общим куском — наложение, а не пересечение. Второй тест — все улицы центра Алматы из OpenStreetMap: 37 315 отрезков в дециметрах со слоями.

Вход

В первой строке число отрезков n (1 ≤ n ≤ 50 000). Дальше n строк: x1 y1 x2 y2 l — концы отрезка и его слой. Все числа целые, |x|, |y| ≤ 10⁶, |l| ≤ 5; концы отрезка различны. Отрезки — куски улиц, и в каждом тесте, кроме небольших, отрезков, которые пересекаются или касаются, гораздо меньше, чем всех пар.

Выход

Два числа через пробел: сколько пар отрезков пересекается в разных слоях и сколько — в одном слое.

Примеры

Пример 1

Вход
12
0 0 10 10 0
0 10 10 0 1
20 0 30 10 0
20 10 30 0 0
40 0 50 0 0
45 0 45 8 0
60 0 70 5 0
70 5 80 0 1
90 0 100 0 0
95 0 110 0 1
0 20 10 20 0
0 22 10 22 0
Выход
1 1

Ограничения

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

Разбор

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

1Подсказка 1

Проверка одной пары — четыре векторных произведения: концы каждого отрезка строго по разные стороны от другого. Беда в числе пар: у 37 тысяч отрезков их почти 700 миллионов. Какие пары можно не проверять вовсе?

2Подсказка 2

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

3Идея

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

4Разбор

Размер клетки c возьмём равным средней длине отрезка по большей из осей. Отрезок с прямоугольником [xmin, xmax] × [ymin, ymax] попадает в клетки от ⌊xmin/c⌋ до ⌊xmax/c⌋ по x и так же по y; клетки храним в хеш-таблице по их номеру. Деление — с округлением вниз и для отрицательных чисел: в Python это //, в Go его нужно написать самому.

Для пары (s, t) в клетке (gx, gy) считаем mx = max(min x у s, min x у t) и так же my. Если ⌊mx/c⌋ ≠ gx или ⌊my/c⌋ ≠ gy, пропускаем: эту пару посчитают в другой клетке. Если прямоугольники не пересекаются, точка (mx, my) может и не попасть ни в одну их общую клетку — тогда пару не посчитает никто, и правильно: такие отрезки не пересекаются.

Затем — строгая проверка пересечения и подсчёт по слоям. На улицах Алматы сетка с клетками в среднюю длину отрезка проверяет меньше тысячной доли всех пар. Ответ на втором тесте — 166 мостов и тоннелей и ни одной ошибки.

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

O(n + P), где P — число пар, оказавшихся в общих клетках. На улицах P — величина того же порядка, что n, но гарантии нет: если все отрезки длинные и тянутся через всё поле, как проспекты в четвёртом тесте, сетка выродится в одну клетку и проверит все пары. Гарантированные O((n + k) log n) для k пересечений даёт заметающая прямая Бентли — Оттмана — о ней отдельная статья.

6Типичные ошибки
  • Все пары подряд. Верно, но 700 миллионов проверок на втором тесте не уложатся во время. Это неверное решение задачи.
  • Пара посчитана в каждой общей клетке. Длинные отрезки лежат во многих клетках, и без правила «только в одной клетке» пересечение посчитается несколько раз. Помогает и множество уже проверенных пар, но оно медленнее и ест память.
  • Касание принято за пересечение. Условие «знаки разные или ноль» засчитает каждую букву Т и каждый общий конец — а на улицах их десятки тысяч. В пятом тесте нет ни одного настоящего пересечения, только касания и наложения.
  • Деление отрицательных. В Go и C++ -7 / 5 равно −1, а не −2, и отрезки слева от нуля попадут не в те клетки.

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

GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи
Каталог алгоритмов