Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Іnstigator

Задача Іnstigator

Маленький мальчик вырезал  из  бумаги в клеточку многоугольник, причем все разрезы шли по сторонам клеток. Ему интересно, за какое время сгорит многоугольник, если поджечь его в некоторой вершине. Бумага горит равномерно во всех направлениях, и скорость распространения огня равна 1 стороне клетки в секунду. Напишите программу, яка определяет, сколько времени пройдет, прежде чем многоугольник сгорит полностью.

 

Технические условия.

Программа Іnstigator   читает с клавиатуры количество вершин многоугольника N (4<=N<=500), а далее -  N пар чисел – координаты  вершин в порядке обхода периметра многоугольника.  Координаты каждой вершины -  два целых числа, не превосходящие по абсолютной величине 10000. Многоугольник поджигается в первой вершине. Описание корректно – стороны многоугольника не имеют общих точек (кроме соседних), каждая вершина соединяет две взаимно перпендикулярные стороны.

Программа выводит  одно действительное число – количество секунд, необходимых для полного сгорания многоугольника. Допустима ошибка, не превосходящая 0,001% от правильного ответа.

Примеры

Ввод

Вывод

4 3 0 3 4 0 4 0 0

0.500E+01

 

Ввод

Вывод

8 1 1 2 1 2 3 4 3 4 5 3 5  3 4 1 4

5.064495

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"