33390번 - Keychain 스페셜 저지다국어

Consider a two-dimensional plane and $n$ points $p_1, \ldots, p_n$ on it. Consider $n$ circles $C_1, C_2, \ldots, C_n$: the $i$-th circle is centered at $p_i$. All the radii of the $n$ circles are $R$.

Determine the minimum value of $R$ such that one can draw another generalized circle $\Gamma$ that intersects all the $n$ circles. Please find one such $\Gamma$ as well.

• A circle $C$ with radius $r$ contains all points such that the Euclidean distance between the point and the center of the circle is exactly $r$.
• A generalized circle is either a circle or a straight line.
• We say two objects $A$ and $B$ intersect if they share a common point.

The first line contains an integer $n$ ($1 \le n \le 3000$). On each of the next $n$ lines, there will be two integers $x_i$ and $y_i$ indicating the coordinates of point $p_i$ ($0 \leq x_i, y_i \leq 10^5$). It is guaranteed that no two given points coincide.

On the first line, print the optimal answer $R_{\mathit{opt}}$.

Your output should satisfy $0 \leq R_{\mathit{opt}} \leq 10^5$.

It can be proved that the minimum value exists and is in this range.

Suppose that $\Gamma_{\mathit{opt}}$ intersects all $C_1,\ldots,C_n$ when $R = R_{opt}$.

It can be shown that, under the constraints in this problem, $\Gamma_{opt}$ can be chosen to be either a circle centered at a rational coordinate, or a straight line with integer coefficients.

• In the circle case, print "C $X$ $Y$ $Z$ $r$", which means that the radius is $r$, and the center of the circle is $O = (X/Z, Y/Z)$. The values $X$, $Y$, $Z$ must be integers with absolute value not greater than $10^{18}$. The value $r$ should be a non-negative real number not greater than $10^{18}$.
• In the straight line case, print "L $a$ $b$ $c$", which means that the line $L$ satisfies the equation $ax + by = c$. The values $a$, $b$, $c$ must be integers with absolute value not greater than $10^{18}$.

When checking your answer, the jury will first check whether $\Gamma_{opt}$ intersects each of the $C$'s. This will be judged by checking:

• if $|R-r|-\varepsilon \leq d(O, p_i) \leq R+r+\varepsilon$ in the circle case ($d(O, p_i)$ is the Euclidean distance between $p_i$ and $O$),
• or $R \leq d(L, p_i) + \varepsilon$ in the line case ($d(L, p_i)$ is the distance from point $p_i$ to line $L$).

Here, $\varepsilon = 10^{-6}$.

After that, your answer will be considered correct if the absolute or relative error between your $R_{opt}$ and jury's $R_{opt}$ doesn't exceed $10^{-6}$.

The first two examples:

Be careful of overflow. Consider using long double or __int128.