Зеркало

Будем находить ответ для каждой стороны отдельно.

Пусть M — рабочее место Стэна, AB - сторона-зеркало. Отразим M относительно прямой AB.

Проведём из получившейся точки M' лучи M'A и M'B. Требуется вычислить площадь пересечения угла AM'B и многоугльника.

Найдём точки D и E — точки повторного пересечения лучей M'A и M'B с границей многоугольника. Для этого бинарным поиском найдём стороны, с которыми пересекается лучи, и найдём точки пересечения.

Затем найдём площадь полученного многоугольника (на рисунке закрашен зелёным). Его стороны — DA, AB, BE, два куска сторон исходного многоугольника (DS и ET) и некоторая непрерывная последовательность сторон исходного многоугольника (от T до S). Чтобы вычислить его площадь, нужно просуммировать ориентированные площади треугольников, образованных каждой из сторон и началом координат. Посчитаем эти площади для сторон DS, DA, AB, BE и ET, а чтобы найти сумму для сторон от T до S, заранее посчитаем частичные суммы на префиксах.

Время работы решения , так как для каждой из n сторон делается два бинарных поиска.