P4586 [FJOI2015] Minimum Double-Circle Cover Problem

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$.

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$.

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

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