Изменения
→Статус
На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
Для упрощения понимания введем два три ограничения на входные данные:
* не существует вертикальных отрезков
* не существует пары отрезков, имеющих более одной общей точки
* никакие три отрезка не пересекаются в одной точке
Как обрабатывать эти случаи , будет объяснено позднее.
==Алгоритм==
===Статус===
[[Файл:pic2.jpg|right|560|thumb|Иллюстрация определения статуса]]
Назовем статусом множество, в которой котором содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченной упорядоченного множества, удаляться из произвольных мест или меняться местами друг с другом.
===Важная мысль===
==Реализация алгоритма==
===Двоичное дерево поиска в качестве статуса===
Из определения статуса ясно, какую структуру удобно использовать в качестве статуса: двоичное дерево поиска. В нем удобно делать все необходимые операции, и выполняться они будут за <tex>O(\log_2(n))</tex>.
===Реализация множества необработанных событий===
