Изменения

Вершин у нас <tex> n </tex>, для каждой вершины мы выполяеем следующие шаги: сортировка (<tex> O(n \log n) </tex>), проверка пересечения (<tex> O(1) </tex>), обновление статуса (суммарно выполняется за <tex> O(n \log n) </tex>, так как мы имеем <tex> O(n) </tex> ребер и каждое ребро мы добавляем и удаляем один раз (вставка происходит за <tex> O(\log n) </tex>, удаление можно сделать за <tex> O(1) </tex>, например, для каждой вершины сохраняя позицию входящих в нее отрезков)). Итого получаеем <tex> O(n) * O(n \log n) = O(n^2 \log n) </tex>. Что и требовалось доказать.|[[Файл:Zamrefr1.png|250px|thumb|right|Обновление статуса заметающего луча]][[Файл:Zamrefr2.png|250px|thumb|right|Обновление статуса заметающего луча]][[Файл:Zamrefr3.png|250px|thumb|right|Обновление статуса заметающего луча]]|}