Изменения

Однако можно это сделать за <tex> O(n ^ 2 \log n) </tex>. Для каждой вершины найдём все видимые из неё вершины при помощи метода плоского заметания. Нам нужно решить следующую задачу: на плоскости дано множество отрезков (рёбер препятствий) и точка <tex> p </tex>. Найти все концы отрезков, видимые из точки <tex> p </tex>. Будем заметать плоскость вращающимся лучом с началом в точке <tex> p </tex>. Статусом заметающей прямой будет отрезки, которые её пересекают, упорядоченные по возрастанию расстояния от точки <tex> p </tex> до точки пересечения. Точками событий будут концы отрезков. Итак, первым делом вершины <tex> w \in W </tex> сортируются по углу между лучом <tex> vw </tex> и вертикальной полуосью, проходящей через <tex> v </tex>. Затем происходит инициализация множества видимых вершин (по умолчанию такое множество пустое). Далее начинается заметание плоскости. В порядке сортировки вершин для каждой из них выполняется проверка: видна ли вершина <tex> w </tex> из вершины <tex> v </tex>. Поскольку такая проверка означает наличие пересеченийДля этого нам достаточно проверить только пересечение с ближайшим отрезком в статусе, которые хранятся а он находится в сбалансированном деревекорне сбалансированного дерева, она может быть выполнена т. е. эта проверка выполняется за <tex> O(\log n1) </tex>. Если вершина видима, необходимо добавить её в список видимых вершин. И, наконец, вне зависимости от видимости вершины, необходимо изменить статус заметающей прямой. Для этого, для текущей вершины <tex> w </tex> необходимо удалить из списка текущих пересечений все рёбра (отрезки), которые заканчиваются в этой вершине (лежат слева от прямой <tex> vw </tex>) и добавить все рёбра (отрезки), которые в ней начинаются (лежат справа от прямой <tex> vw </tex>).

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