Изменения

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

for Vertex w in getVisibleVertices(v, segments) //добавляем в граф все видимые из нее вершины

vector<Vertex> getVisibleVertices(vertex v, set<segment> segments)// Инициализируем статус vector<Vertex> answer, currentVerticesfor segment s in segments if intersection s and ray from v to up exists currentVertices status.add(all w s)// Инициализируем множество вершин, которые нужно рассматривать for point p in vertices : wsegments if p.x >= v.x currentVertices.add(p) //рассматриваем только вершины правее v sort vertexes (currentVertices) by angle //в порядке увеличения угла с //вертикальной прямой, проходящей через v heap<Segment> status status.add(all e in Edges : intersection(eДля каждой вершины проверяем, l) != null) //инициализируем видима ли она и обновляем статус

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

Вершин у нас В качестве статуса нужно использовать структуру данных, позволяющую добавлять и удалять из нее отрезки за <tex> O(\log n ) </tex>, для каждой вершины мы выполяеем следующие шаги: сортировка и извлекать минимум за <tex> O(1) </tex> или <tex> O(n \log n) </tex>), проверка пересечения (. В этом случае достигается асимптотика <tex> O(1n^2 \log n) </tex>), обновление статуса так как для каждой из <tex> n </tex> точек выполняется сортировка(суммарно выполняется за <tex> O(n \log n) </tex>), так как мы имеем обновление статуса (суммарно <tex> O(n \log n) </tex> ребер , так как каждый отрезок добавляется и каждое ребро мы добавляем и удаляем удаляется из статуса только один раз ) и запросы ближайшего отрезка (вставка происходит за <tex> O(\log n) </tex>, удаление можно сделать за или <tex> O(1) </tex>на точку, например, для каждой вершины сохраняя позицию входящих в нее отрезков). Итого получаеем то есть <tex> O(n) * O(n \log n) = </tex> или <tex> O(n^2 \log n) </tex>. Что и требовалось доказать).