Мытищинская школа программистов

Задача №2533. А олени — лучше!

Решение для верёвки не длиннее полупериметра:

Область представляет собой объединение нескольких секторов окружностей разного радиуса.

Если точка находится на стороне, то первый сектор — это полуокружность радиуса, равного длине верёвки.

Следующие сектора имеют меньший радиус. Радиус уменьшается по мере удаления от стартовой точки.

Вычисление площади сектора:

Угол сектора равен углу между векторами последовательных вершин.

В случае, когда ограда является прямоугольником, угол всегда равен 90°. Поэтому площадь сектора равна четверти площади окружности.

Площадь сектора окружности радиуса \(R\) с углом \(\beta\) равна \(\beta R^2/2\).

Решение для верёвки длиннее полупериметра:

Области, покрытые слева и справа, начинают пересекаться.

Необходимо найти точку, в которой они начнут пересекаться, и позиции, в которых пересекаются сектора. Для этого переберём все пары секторов и найдем наиболее раннюю пару пересекающихся.

Ответ состоит из трёх компонент:

Сумма площадей секторов до момента пересечения.

Сумма двух последних секторов, идущих до точки пересечения.

Сумма треугольников с вершинами: точка пересечения и две последовательные точки многоугольника.

Самый простой способ выбора ближайшего пересечения — это посчитать искомую площадь при предположении каждого пересечения. Из полученных результатов выбрать минимум.

Сдать: для сдачи задач необходимо войти в систему