22174번 - Парад 스페셜 저지다국어

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

Из года в год парад проходит на площади, имеющей форму выпуклого n-угольника. Многолетний опыт проведения этого мероприятия показывает, что для повышения зрелищности площадь должна быть разбита на k секторов следующим образом: выбирается точка, которая будет считаться центром площади, и от нее к краям натягиваются система из нескольких гирлянд. Известно также, что угол между каждой парой соседних гирлянд должен быть равен строго определенной величине (для разных пар, возможно, разной). При этом правительство желает минимизировать суммарную длину всех гирлянд с тем, чтобы сэкономить средства. Единственный способ как-то повлиять на суммарную длину гирлянд заключается в повороте всей системы гирлянд на некоторый угол относительно выбранного центра площади. Требуется определить минимальную возможную сумму длин всех гирлянд.

На рисунке слева изображен тест из примера в том виде, в котором он задан во вводе, а справа — он же после оптимального поворота.

Первая строка входных данных содержит одно целое число n (3 ≤ n ≤ 30) — количество вершин многоугольника, форму которого имеет площадь. Следующие n строк содержат координаты вершин многоугольника. Вершины описаны в порядке обхода против часовой стрелки. Все координаты вершин целые и по модулю не превышают 10000. Заданный многоугольник является невырожденным и выпуклым. Никакие три его вершины не лежат на одной прямой.

Следующая строка содержит координаты центра площади, его координаты также целые и гарантируется, что он находится строго внутри площади.

Следующая строка входных данных содержит одно целое число k (1 ≤ k ≤ 30) — количество гирлянд, которые должны быть натянуты. Последняя строка содержит описание одного из возможных расположений гирлянд: для каждой дан угол в градусах, на который она повернута против часовой стрелки относительно положительного направления оси Ox. Все углы измеряются целым числом градусов от 0 до 359.

Выведите одно вещественное число — минимальную сумму длин гирлянд после поворота всей системы гирлянд на некоторый угол. Ответ должен быть выведен с точностью не хуже 10^-5.

При этом разрешается повернуть систему на любой угол, он не обязательно должен измеряться целым числом градусов.