Как найти все пары пересекающихся отрезков эффективнее, чем O(n^2)? Идея заметающей прямой
Умею проверять пересечение двух отрезков. Но в задаче дано n отрезков и нужно понять, есть ли среди них хоть одна пересекающаяся пара (или найти все). Наивно это O(n^2) проверок. Какая идея позволяет ускорить и за сколько?
2 ответа
Классика — алгоритм заметающей прямой (sweep line) Бентли–Оттмана. Вертикальная прямая движется слева направо; в каждый момент она хранит активные отрезки, упорядоченные по y в точке пересечения с прямой (в сбалансированном set/дереве).
Идея в том, что пересекаться могут только отрезки, соседние по y в этом порядке. Поэтому вместо всех пар проверяем лишь пары «сосед сверху / снизу» при трёх типах событий:
- левый конец отрезка → вставляем его в порядок, проверяем с новыми соседями;
- правый конец → удаляем, проверяем, не пересеклись ли его бывшие соседи между собой;
- точка пересечения → меняем местами два отрезка, проверяем их с новыми соседями.
Сложность O((n + k) log n), где k — число пересечений. Для задачи «есть ли хоть одно пересечение» останавливаемся на первом найденном — это O(n log n).
Геометрическая проверка соседей — тот самый segInter через четыре ориентации. Сортировка событий по x (с тай-брейками) — основа всего.
Честная реализация Бентли–Оттмана с динамическими событиями-пересечениями довольно муторная (нужна очередь событий + аккуратные сравнения отрезков в set с пересчётом при движении прямой), и на олимпиаде её редко пишут целиком. Но упрощённая версия для вопроса «есть ли пересечение?» заметно проще: события только концы отрезков, поддерживаем активные отрезки в set, при вставке/удалении проверяем лишь верхнего и нижнего соседа. Это уже ловит факт наличия пересечения за O(n log n) для большинства расположений.
Грабли: вертикальные отрезки (бесконечный наклон — обрабатывай как частный случай или поверни плоскость на чуть-чуть), совпадающие x у концов (нужны строгие тай-брейки в сортировке событий), и точность сравнения отрезков по y — здесь как раз соблазн double, который лучше заменить целочисленным сравнением через cross. Если просто нужно посчитать число пересечений малого n — наивный O(n^2) с segInter тоже часто проходит, не усложняй без нужды.