0413. Побег

Имя входного файла:	escape.in
Имя выходного файла:	escape.out
Ограничение по времени:	1 s
Ограничение по памяти:	256 megabytes

Слон Бролефант - старый друг Ярополка, друга Святослава. Недавно слон отправился в путешествие в родную Индию и был пленен злым раджей Небронашем. Слухи об этом подлом преступлении дошли до Ярополка, и теперь он отправляется в Индию, чтобы выручить друга в беде. Святослав конечно же ему помогает. Оказывается, Бролефанта держат в тюрьме, которая имеет форму выпуклого многоугольника из N вершин и находится рядом со дворцом Небронаша. Ярополк выяснил, что в углах многоугольника стены тюрьмы очень уязвимы, поэтому в них можно легко сделать отверстие достаточное по размеру для прохода слона. Святослав проследил за охранниками и узнал, что они в полдень каждого дня помещают Бролефанта рядом с некоторым углом k и расходятся обедать. Святослав и Ярополк решили, что сразу после полудня они воспользуются уязвимостью одного из углов и подадут звуковой сигнал, сообщающий об этом Бролефанту. Бролефант, услышав сигнал, начнет бежать вдоль забора (иначе его заметят со стены), он всегда бежит против часовой стрелки. Для дальнейшего планирования побега Святославу нужно знать среднее значения M_k расстояния от угла k до угла с отверстием, при условии, что угол для отверстия выбирается произвольно с равной вероятностью. Святославу не удалось узнать настоящее значение k, поэтому требуется найти M_k для всех возможных k.

Формат входного файла

В первой строке входного файла содержатся одно число N – количество углов у забора. 3 ≤ N ≤ 50000. В каждой из N следующих строк содержится два числа x, y – координаты углов забора в порядке обхода. -10⁹ ≤ x, y ≤ 10⁹

Формат выходного файла

В единственной строке выведите N чисел M_k с точностью не менее 4 знаков после запятой.

Пример:

escape.in	escape.out
4 0 0 1 0 1 1 0 1	1.5 1.5 1.5 1.5

Источник: Чемпионат ПетрГУ по программированию. 1 марта 2015 года

Обсудить       Отправить решение



Версия для печати