— Ой, Шеф, а я вас вижу!
— Аналогично!
Расследуя своё очередное дело, Шеф и Коллега забрались на пустой
склад, чтобы внимательно его изучить в поисках улик.
Склад представляет собой многоугольник без самопересечений и самокасаний (но не обязательно
выпуклый). На каком максимальном расстоянии друг от друга могут находиться
Шеф и Коллега, не покидая территорию склада и не теряя друг друга из виду?
Сыщики видят друг друга, если все точки отрезка,
соединяющего их, лежат внутри или на границе склада.
Исходные данные
В первой строке записано единственное целое число n — количество вершин многоугольника (3 ≤ n ≤ 200).
Далее в n строках перечислены пары координат вершин xi, yi в порядке по или против часовой стрелки.
Координаты вершин — целые числа в пределах от −1000 до 1000.
Гарантируется, что многоугольник не имеет ни самопересечений, ни самокасаний.
Результат
Выведите максимальное искомое расстояние c абсолютной или относительной
точностью не менее 10−6.
Пример
исходные данные | результат |
---|
4
0 0
0 1
1 1
1 0
| 1.414214
|
Автор задачи: Михаил Рубинчик (подготовка — Егор Щелконогов)
Источник задачи: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013