0413. Побег

Input file name:	escape.in
Output file name:	escape.out
Time limit:	1 s
Memory limit:	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

Discuss       Submit a solution



Printable version