P4586 [FJOI2015] 最小覆盖双圆问题

题目描述

给定平面上 $n$ 个点 $(x_1,y_1),...,(x_n,y_n)$,找出2个半径相同的圆 $R_1$ 和 $R_2$,覆盖给定的 $n$ 个点,且半径最小。 ![](https://cdn.luogu.com.cn/upload/pic/18767.png) 设计一个算法,计算出所求最小覆盖双圆 $R_1$ 和 $R_2$ 的半径。

输入格式

输入有多个测试实例。每个实例的第一行中给出正整数 $n$,表示平面上有 $n$ 个点。 接下来的 $n$ 行中每行给出两个实数 $x, y$。 最后一行有一个 $0$ 表示结束。

输出格式

对于每组数据,输出最小的符合题意的圆的半径,保留两位小数。

说明/提示

对于 $100\%$ 的数据,$n \leq 1000$,$|x_i|,|y_i| \leq 10^5$,$T \leq 10$。