Изменения

Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка <tex> v </tex>. Найти все концы отрезков, видимые из точки <tex> v </tex>.  

 Итак, первым делом вершины <tex> w \in V </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v </tex> {{---}} луч <tex> l </tex> (достаточно рассматривать только точки, которые лежат правее <tex> v </tex>, так как все точки левее мы уже рассмотрели). Инициализируем Затем инициализируем статус отрезками, которые пересекают луч <tex> l </tex>. Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v </tex>. Для этого нам достаточно проверить только пересечение заметающего луча с ближайшим отрезком в статусе. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающего луча. Для этого для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений статуса все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

Set<Vertex> vertices = getVertices(segments) //получаем все вершины препятствий vertices.add(s, t) //добавляем начальную и конечную вершину graph visibilityGraph(vertices) //изначально в графе только вершины for Vertex v in vertices //для каждой вершины for Vertex w in getVisibleVertices(v) // добавляем в граф все видимые из неевершины

currentVertices.add(all w in vertices : w.x >= v.x) //рассматриваем только вершины правее v sort vertexes by angle //в порядке увеличения угла с // вертикальной прямой, проходящей через v

status.add(all e in Edges : intersection(e, l) != null) //инициализируем статус

if intersection(vw, status.closest) == null //если отрезок vw не пересекает ближайший // отрезок в статусе answer.add(w) // добавляем в ответ delete from status all edges ending in w //обновляем статус

Вершин у нас <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>. Что и требовалось доказать.