4948 - [Wf2017]Airport Construction

位于热带的 Piconesia 岛国以其秀丽的沙滩、繁茂的植被、可可与咖啡原料的产出以及全年宜人的天气而闻名海 外。天堂般美丽的这里将纳入未来举办 ACM-ICPC 世界总决赛的地点考虑名单中(至少也会是执行委员会度假地点 的选择之一) 。但是还有一个小问题:这个岛真的很难到达。就目前而言,最快的方式是从最近的机场出发,并借助 渔船、油轮、皮划艇和潜艇这些工具,花费三天时间才能到达小岛。为了让大家更轻松地参加 ICPC 世界总决赛,也 为了推动小岛的旅游业发展,Piconesia 正在计划修建它的第一个机场。考虑到越长的起降跑道越有助于对大型飞 机的支持, Piconesia 决定在其岛上修建一条最长的起降跑道带。不幸地是,他们无法确定这条跑道应该设置在哪 里。也许你可以帮个忙?对于本题,我们将 Piconesia 的边界抽象成一个多边形的模型。根据这个多边形,你需要计 算出最长的跑道长度(即最长的线段)使得跑道可以完全在小岛上修建。图 1 对应于第一个输入样例。

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

输入

第一行包含一个整数 n (3 ≤ n ≤ 200) ,表示多边形的点数。 接下来 n 行,每行包含两个整数 x 和 y (|x|, |y| ≤ 10^6 ) ,表示多边形上的顶点 (x, y) 顶点按照逆时针顺序给出。 给出的多边形是简单多边形,即它的顶点互不相同,并且除了相邻的两条边在公共点相交之外 它的任意两条边都不会相交。此外,相邻的两条边也不会共线。

输出

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

样例

输入

样例1
7
0 20
40 0
40 20
70 50
50 70
30 50
0 50
样例2
3
0 2017
-2017 -2017
2017 0

输出

样例1
76.157731059
样例2
4510.149110617
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题