#P2403. [Balkan 2011]2circles

    ID: 1448 传统题 1000ms 128MiB 尝试: 23 已通过: 4 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案实数二分计算几何半平面交半平面按角排序旋转卡壳叉积平方距离比较CF2500鸣谢Lyuu

[Balkan 2011]2circles

题目描述

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

输入格式

第一行一个整数 NN 。

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

输出格式

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

只要你的输出与标准答案的误差在 10−310^{-3} 以内均被视为通过。

4
0 0
1 0
1 1
0 1
0.293

样例说明 1

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

此时半径为 22×(1+2)≈0.293\frac{\sqrt{2}}{2\times(1+\sqrt{2})} \approx 0.293 。

4
0 0
3 0
3 1
0 1
0.500
6
0 0
8 0
8 6
4 8
2 8
0 4
6
0 0
8 0
8 6
4 8
2 8
0 4

数据规模与约定

对于 10%10\% 的数据,保证 N=3N=3 。

对于 40%40\% 的数据,保证 N≤250N\le 250 。

对于 100%100\% 的数据,保证 $3\le N \le 5\times 10^4 , -10^7 \le x_i,y_i \le 10^7$ 。

题目来源

Balkan Olympiad in Informatics 2011 Day 1 T1 2circles