#P51860. 「ICPC World Finals 2017」机场构建 Airport Construction

「ICPC World Finals 2017」机场构建 Airport Construction

题目描述

位于热带的 Piconesia 岛国以其秀丽的沙滩、繁茂的植被、可可与咖啡原料的产出以及全年宜人的天气而闻名海外。天堂般美丽的这里将纳入未来举办 ACM-ICPC 世界总决赛的地点考虑名单中(至少也会是执行委员会度假地点的选择之一)。但是还有一个小问题:这个岛真的很难到达。

就目前而言,最快的方式是从最近的机场出发,并借助渔船、油轮、皮划艇和潜艇这些工具,花费三天时间才能到达小岛。为了让大家更轻松地参加 ICPC 世界总决赛,也为了推动小岛的旅游业发展,Piconesia 正在计划修建它的第一个机场。

考虑到越长的起降跑道越有助于对大型飞机的支持,Piconesia 决定在其岛上修建一条最长的起降跑道带。不幸地是,他们无法确定这条跑道应该设置在哪里。也许你可以帮个忙?

对于本题,我们将 Piconesia 的边界抽象成一个多边形的模型。根据这个多边形,你需要计算出最长的跑道长度(即最长的线段)使得跑道可以完全在小岛上修建。图 1 对应于第一个输入样例。

图 1. 小岛的多边形模型。最长的跑道已用粗线标出。

输入格式

第一行包含一个整数 nn (3n200)(3 \leq n \leq 200),表示多边形的点数。

接下来 nn 行,每行包含两个整数 xxyy (x,y106)(|x|, |y| \leq 10^6),表示多边形上的顶点 (x,y)(x, y),顶点按照逆时针顺序给出。

给出的多边形是简单多边形,即它的顶点互不相同,并且除了相邻的两条边在公共点相交之外,它的任意两条边都不会相交。此外,相邻的两条边也不会共线。

输出格式

输出能放进给定多边形内部的最长线段长度,其绝对误差或相对误差不能超过 10610^{-6}

样例 1

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50
76.157731059
3
0 2017
-2017 -2017
2017 0
4510.149110617