#6409. 「ICPC World Finals 2018」熊猫保护区

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

上个月,四川省投资建设大熊猫国家公园,是一个容纳超过 1800 只大熊猫的自然保护区。公园会被一个多边形栅栏包围。为了帮助研究人员跟踪熊猫,多边形的每个顶点上会有一个无线电接收器,且每个动物都会装备上无线电传输设备。每个无线电接收器会覆盖以接收器为中心的一个圆形区域,且所有接收器的区域大小相同。接收器区域大小越小,价格自然越便宜,所以你的任务是确定最小的覆盖整个公园所需要的半径。

举例来说,下图为第一个样例输入所描述的公园。注意到半径为 35 不足以覆盖整个公园,而 50 的是最少的覆盖整个公园需要的半径。

sample.png

输入格式

第一行有一个整数 n (3 \le n \le 2000) 表示多边形的顶点个数。接下来 n 行,每行两个整数 x y (\lvert x \rvert, \lvert y \rvert \le 10^4) 按照顺时针顺序给出多边形的各个顶点。

多边形是简单多边形;也就是说,顶点各不相同,且除了相邻的边相交于多边形的顶点以外,没有任何两条边相交或接触。

输出格式

输出覆盖整个公园需要的最小无线电半径,绝对误差或相对误差不超过 10^{-6} .

样例

样例输入 1

5
0 0
170 0
140 30
60 30
0 70

样例输出 1

50

样例输入 2

5
0 0
170 0
140 30
60 30
0 100

样例输出 2

51.538820320

样例输入 3

5
0 0
1 2
1 5
0 2
0 1

样例输出 3

1.581138830