Задача І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
|
|
