Изменения
Нет описания правки
Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>X</tex>. Внимательный читатель сейчас наверное воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>Здесь должна быть анимашка, в которой показывается, что все будет корректно.
===Несколько отрезков в одной точке===
====Первый метод решения проблемы====
У нас есть упорядоченное множество необработанных событий. Давайте перед добавлением события будем проверять, а нет ли его там. Если оно там уже есть, то события вида "в этой точке перечекаются отрезки <tex>A</tex> и <tex>B</tex>", превратится в событие вида "в этой точке пересекаются отрезки <tex>A</tex>, <tex>B</tex> и <tex>C</tex>". В процессе обработки этой точки порядок следования в статусе всех отрезков, пересекающихся в ней, просто инвертируется. Соответственно, проблема решилась.
====Второй метод решения проблемы====
На самом деле, посмотрим более внимательно, что произойдет в этой точке. Все пересечения всех пар обработаются. Всего таких пар <tex>k^2</tex>, где в точке пересекается <tex>k</tex> отрезков. Если в некой перестановке делается <tex>k^2</tex> элементарных транспозиций, и ни одна из них не повторяется, то перестановка становится инвертированной. Так что, даже если оставить все как есть, то все будет работать. <s>Такие дела.</s> Здесь тоже должна быть соответствующая анимашка.
===СНМ вместо отрезков===
'''Внимание! Этот раздел должен интересовать только <s>задротов</s> любознательных, так как он описывает разбор случая, который нам, по обещанию Ковалева, не встретится.'''
