Тёмыч выгуливает своего любимого козла в соседском огороде с капустой. Тёмычу понадобилось отлучиться на минутку, и он решил вбить в землю колышек и привязать козла к нему, дабы он не съел всю соседскую капусту. Чтобы животное не умерло с голоду, Тёмыч хочет выбрать для колышка такое место в огороде, а также подобрать веревку такой длины, чтобы в распоряжении козла была как можно большая площадь огорода. Однако есть небольшая проблема: козел, будучи оставленным наедине с огородом, пытается пробить рогами дыру в изгороди, окружающей огород. Ему удается это сделать, если он достает рогами до изгороди и при этом на веревке есть хотя бы маленькая слабина. Тёмыч не хочет, чтобы соседи увидели следы пребывания в своем огороде непрошеных гостей, поэтому пытается привязать козла так, чтобы изгородь осталась в целости и сохранности. Помогите ему сделать это. Вам нужно только найти необходимую длину веревки, а место для колышка Тёмыч найдет сам.
Исходные данные
Соседский огород имеет форму многоугольника (не обязательно выпуклого) с N вершинами. В первой строке находится число N (3 ≤ N ≤ 25). В следующих N строках перечислены координаты вершин многоугольника в порядке обхода против часовой стрелки: в (i+1)-й строке через пробел указаны координаты xi и yi — целые числа в пределах от 0 до 1000. Огород настолько велик, что вы можете считать козла материальной точкой.
Результат
Выведите единственное число R — длину веревки, на которую Тёмыч привяжет козла (R должно быть округлено до 2 знаков после десятичной точки).
Пример
исходные данные | результат |
---|
3
0 0
200 0
0 200 | 58.58 |
Автор задачи: Александр Ипатов
Источник задачи: Petrozavodsk summer training camp, August 2005.