Изменения
Нет описания правки
Как обрабатывать эти случаи будет объяснено позднее.
==Алгоритм==
===Основная идея===
Алгоритм будет основан на идее сканирующей прямой. Опишем три типа событий, которые мы и будем обрабатывать:
* начался новый отрезок
* два отрезка пересеклись
* отрезок закончился
Сканирующая прямая будет расположена параллельно оси ординат, и двигаться вдоль оси абсцисс в сторону ее положительного направления. Учитывая введенные ограничения на входные данные, прямая никогда не будет проходить через два события одновременно. ===Статус===Назовем статусом структуру данных, в которой содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этой упорядоченной структуры, удаляться из произвольных мест или меняться местами друг с другом. Соответственно, нам идеально подходит структура данных дерево поиска, но это уже совсем другая история.
