Description

Given $n$ points on the plane $(x_1, y_1), \ldots, (x_n, y_n)$, find two circles $R_1$ and $R_2$ with the same radius that cover all the given $n$ points, and the radius is as small as possible.

Design an algorithm to compute the minimal radius of the two covering circles $R_1$ and $R_2$.

Input Format

The input contains multiple test cases.
For each case, the first line contains a positive integer $n$ ($n < 1000$), indicating there are $n$ points on the plane.
Each of the next $n$ lines contains two real numbers $x$ and $y$, with $-100000 \le x \le 100000$ and $-100000 \le y \le 100000$.
The input ends with a line containing a single $0$.

Output Format

For each test case, output the minimal radius of a circle that satisfies the requirement, keeping two decimal places.

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

0.50
3.05

Hint

For 100% of the testdata, $n \le 1000$, $|x_i|, |y_i| \le 100000$, and $T \le 10$.

Translated by ChatGPT 5