Пересечение набора отрезков плоскости

1: Поиск всех пересечений отрезков
Задача 2: Проверка пересечения хотя бы

перекрываются ли какие-нибудь два из них.

Сложность: O(N logN)

пересечения отрезков: Θ(N logN)

в абсциссе x, если вертикаль, проходящая через x, пересекает оба

u

v

s2 и s3 сравнимы в абсциссе u
s1 и s3 сравнимы в абсциссе v
s1 и s3 не сравнимы в абсциссе u
s2 и s3 не сравнимы в абсциссе v

s2, s2 >v s4, s1 >v s4
s3 не сравним ни

Отрезок s1 выше отрезка s2 в х (пишется s1 >x s2), если s1 и s2 сравнимы в х, и точка пересечения s1 с вертикалью x лежит выше точки пересечения s2 с ней же.

Встретился левый конец отрезка
Встретился правый конец отрезка
Обнаружена точка

(s3, s2, s1)