Автор задачи: Даниил Орешников, разработчик: Константин Бац
Давайте заметим, что весь «свет» (паутина), исходящий из начала координат, разбивается на сектора, и каждый из секторов либо достигает внешней окружности, либо поглощается по пути. Для того, чтобы вычислить ответ на задачу, достаточно найти сумму углов всех секторов, которые достигают внешней окружности, и поделить на $$$2 \pi$$$ ($$$360^\circ$$$). А секторов в принципе не так много: каждое препятствие (дыра) задает определенный сектор, который им поглощается — он расположен между касательными к этому препятствию из начала координат. Соответственно, поглощаемых секторов не более $$$n$$$, а значит всего секторов не более $$$2n$$$.
Осталось научиться определять эти сектора. Сначала рассмотрим простую версию: пусть по направлению нулевого угла (ось $$$Ox$$$) нет препятствий. Тогда воспользуемся стандартной техникой 1D-сканирующей прямой или «сортировки событий» и заведем события вида «в направлении угла $$$\alpha$$$ располагается касательная к препятствию». Каждое событие будет характеризоваться этим углом $$$\alpha$$$ и флагом $$$+1$$$, если центр препятствия имеет больший полярный угол, и $$$-1$$$ иначе. Теперь отсортируем эти события и обработаем в порядке возрастания угла. Получится некоторый «сканер» в виде луча из начала координат, который поворачивается против часовой стрелки.
Заметим, что когда мы встречаем событие с флагом $$$+1$$$, это означает, что после добавится новое препятствие, и наоборот — при обработке события $$$-1$$$ препятствий на пути луча становится на $$$1$$$ меньше. Будем поддерживать количество препятствий по направлению луча $$$c$$$, и при встрече нового события обновлять его как $$$c \gets c + \mathtt{flag}$$$. Теперь осталось только посчитать ответ — суммарный угол всех секторов, в которых $$$c$$$ было равно $$$0$$$, то есть на пути луча не было препятствий. Для этого:
Теперь стоит упомянуть две детали. Во-первых, при сортировке векторов по углу полезно использовать векторное произведение, чтобы не вычислять углы напрямую — это поможет избежать ошибок из-за погрешности (хотя в данной задаче касательные к препятствиям уже имели нецелые координаты, так что конкретно в этой задаче в этом не было большого смысла). Во-вторых, мы решили задачу, исходя из того, что в нулевом направлении нет препятствий. Если это не так, решение не сильно изментится: либо можно отдельно посчитать исходный $$$c$$$ как количество препятствий на пути за $$$\mathcal{O}(n)$$$, отдельно проверив каждое препятствие, либо можно считать «свободными» все сектора, в которых $$$c$$$ достигает своего глобально минимального значения.
Время работы решения — $$$\mathcal{O}(n \log n)$$$ на сортировку событий.