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.