ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1853. Лазерные технологии

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Почти в любой сувенирной лавке можно найти стеклянные шары или кубы с узорами внутри. Юной Ане всегда было интересно, как производят эти сувениры, поэтому она пошла учиться на факультет лазерных технологий. Там она узнала, что если пересечь внутри стеклянной заготовки два лазерных луча частоты 3.1415 ПГц, то стекло в точке пересечения станет мутным на вид, хотя на прохождение лазерных лучей это помутнение никак не повлияет.
Сейчас Аня хочет сама нарисовать какой-нибудь узор внутри многоугольной призмы. Она решила начать с плоской картинки в сечении, параллельном основанию призмы. Но вот беда — второй лазер сломался после того, как Аня случайно пролила на него чашку чая. Впрочем, Аня выяснила, что если два последовательных импульса лазера пройдут через одну точку через очень короткий промежуток времени, то стекло в этой точке также помутнеет. Теперь она хочет перемещать источник лазера равномерно вдоль периметра сечения призмы, пока он не опишет весь периметр. Луч лазера во время его движения всё время должен лежать в плоскости выбранного сечения. Чтобы лазер не прожёг что-нибудь лишнее, его луч следует направлять строго в приёмник.
Поскольку частота импульсов лазера очень высока, помутневшие точки будут расположены настолько плотно, что для невооружённого глаза будут образовывать участки непрерывных линий. Аня хочет узнать суммарную длину всех этих линий, для этого она обратилась за помощью к вам.
Сечение призмы является выпуклым n-угольником. В начальный момент времени Аня размещает источник лазерного луча в некоторой точке периметра сечения, а приёмник луча — в некоторой другой точке периметра. Расстояние между этими точками вдоль периметра сечения равняется d. После этого Аня перемещает источник и приёмник луча вдоль периметра с одинаковой и постоянной скоростью в одном и том же направлении обхода. Узор будет готов, когда источник и приёмник вернутся в свои исходные позиции.
Problem illustration
Дадим формальное определение кривым, образованным помутневшими точками. Пусть в некоторый момент времени t источник находится в точке A, а приёмник — в точке B. В момент времени t + ε источник, следуя вдоль периметра, перемещается в точку A', а приёмник — в точку B'. В общем случае отрезки AB и A'B' имеют ровно одну точку пересечения. Если ε → 0, то эта точка является точкой, помутневшей в момент времени t. Все точки, помутневшие в какой-либо момент времени, образуют набор кривых, суммарную длину которых вам нужно найти.
На иллюстрации периметр сечения является квадратом, лазерные лучи в различные моменты времени обозначены пунктиром, а точки, в которых стекло помутнеет, выделены жирным. Расстояние между источником и приёмником, измеренное вдоль периметра, при их движении остаётся равным d. Обратите внимение, это не означает, что длины пунктирных отрезков равны. На рисунке видно, что помутневшие точки лежат на некоторой кривой.

Исходные данные

В первой строке дано целое число n (3 ≤ n ≤ 10 000). Далее в n строках расположены пары целых чисел — координаты вершин многоугольника в порядке обхода против часовой стрелки. Координаты целые и по модулю не превосходят миллиона.
В последней строке записано целое положительное число d. d не превосходит половины периметра многоугольника и строго больше максимальной из его сторон.

Результат

Выведите суммарную длину всех линий, образованных помутневшими точками, с абсолютной или относительной погрешностью не более 10−6.

Примеры

исходные данныерезультат
3
-1 0
1 0
0 10
11
22.3730148246
4
0 0
10 0
10 10
0 10
11
56.1255583559
Автор задачи: Денис Дублённых
Источник задачи: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011