logo AlgoBeat OnlineJudge
登录 注册

#102403. [BZOJ 2403] [Balkan 2011]2circles

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定一个 个顶点的凸多边形,求最大的 ,使得两个半径为 的圆,在互不相交的情况下能被放入到这个多边形中。

输入格式

第一行一个整数

接下来的 行,每行两个空格分开的整数 ,表示凸多边形第 个顶点的坐标。(保证顶点坐标按逆时针顺序给出)

输出格式

一个实数,表示最大的半径

只要你的输出与标准答案的误差在 以内均被视为通过。

样例

样例输入 #1

4
0 0
1 0
1 1
0 1

样例输出 #1

0.293

样例说明 1

将两个圆心放在该正方形的对角线上的时候,半径最长,如图:

此时半径为

样例输入 #2

4
0 0
3 0
3 1
0 1

样例输出 #2

0.500

样例输入 #3

6
0 0
8 0
8 6
4 8
2 8
0 4

样例输出 #3

6
0 0
8 0
8 6
4 8
2 8
0 4

数据范围与提示

对于 的数据,保证

对于 的数据,保证

对于 的数据,保证

Balkan Olympiad in Informatics 2011 Day 1 T1 2circles