Изменения
add definition
Введем некоторые обозначения. Пусть <tex>Int(S)</tex> - множество всех точек пересечения отрезков из множества <tex>S</tex>, а <tex>K = |Int(S)|</tex> - количество таких пересечений ;<br>
Через <tex>\langle a, b, e \rangle</tex> обозначим вертикальную полосу, которая ограничена прямыми <tex>x = ba</tex> и <tex>x = eb</tex>, а через <tex>s</tex> отрезок с концами абсцисс <tex>l</tex> и <tex>r</tex>.<br>Рассмотрим взаимное расположение вертикальной полосы <tex>\langle a, b, e \rangle</tex> и отрезка <tex>s</tex>.
{{Определение
|definition=
Будем говорить, что отрезок <tex>s</tex>, с концами абсцисс <tex>l</tex> и <tex>r</tex> :
- '''содержит'''(span) полосу <tex>\langle a, b, e \rangle</tex>, если <tex>l \le b a \le e b \le r</tex>; <br>- '''внутренний'''(inner) для полосы <tex>\langle a, b, e \rangle</tex>, если <tex>b a < l < r < eb</tex>; <br>- '''пересекает'''(cross) полосу <tex>\langle a, b, e \rangle</tex> в других случаях.
}}
Два отрезка <tex>s_1</tex> и <tex>s_2</tex> называются пересекающимися внутри полосы <tex>\langle a, b, e \rangle</tex>, если их точка пересечения лежит в пределах этой полосы. <br>
Для двух множеств отрезков <tex>S</tex> и <tex>S'</tex> определим множество <tex>Int(S, S')</tex> как <tex>\{ {s, s'} | (s \in S, s' \in S') \& (s \ intersect \ s') \}</tex>.
Обозначения <tex>Int_{a, b, e}(S)</tex> и <tex>Int_{a, b, e}(S, S')</tex> будут использоваться для описания подмножеств <tex>Int(S)</tex> и <tex>Int(S, S')</tex>, состоящих из пересекающихся пар отрезков в пределах полосы <tex>\langle a, b, e \rangle</tex>. Далее скобки <tex>\{\}</tex> используются для определения неупорядоченных наборов, а скобки <tex>()</tex> используются для определения упорядоченных множеств.
Введем отношение порядка на множестве отрезков <tex>s_1 <_b s_2</tex> если оба отрезка пересекают вертикальную линию <tex>x = a</tex> и
точка пересечения этой прямой с отрезком <tex>s_1</tex> лежит ниже точки пересечения с <tex>s_2</tex>.
==Алгоритм==
