#P4138. [FJOI2015]最小覆盖双圆问题

[FJOI2015]最小覆盖双圆问题

[FJOI2015] 最小覆盖双圆问题

题目描述

给定平面上的 nn 个点,用两个半径相同的圆盘覆盖这些点,使公共半径尽可能小。每个点只需在至少一个圆盘内或其边界上,两个圆盘允许重叠。

利用两个等半径圆盘覆盖平面点集

输入格式

输入包含多组数据,至多 1010 组。每组先输入一个整数 nn(1≤n≤1 0001\le n\le1\,000),再输入 nn 行,每行两个实数 x,yx,y(∣x∣,∣y∣≤100 000|x|,|y|\le100\,000),表示一个点的坐标。

输入以单独一行的 0 结束。

输出格式

对每组数据输出一行,给出最小公共半径,保留两位小数。

评测按与真实最优半径的绝对误差不超过 0.0050.005 检查。若最优值恰好处于两个相邻的两位小数之间,两种舍入方向均可。

样例 #1

样例输入 #1

3 
0.00 0.00 
1.00 0.00 
0.00 4.00 
10 
0.00 0.00 
0.00 3.00 
1.00 6.00 
2.00 2.00 
3.00 5.00 
5.00 3.00 
6.00 3.00 
9.00 5.00 
10.00 5.00 
11.00 3.00 
0

样例输出 #1

0.50
3.05