Minimum Covering Circle for K Points

Given N points in the plane and an integer K, find the circle with the minimum possible radius that covers at least K of these points. The output should include the minimum radius and the coordinates of the circle's center. All formulas must be in LaTeX format. In particular, if a circle determined by candidate points has center \( (cx, cy) \) and radius \( r \), then it must satisfy \( \sqrt{(x-cx)^2+(y-cy)^2} \leq r+10^{-9} \) for at least K points.

The candidate circles can be determined by one point, two points, or three points. For instance, the circle defined by two points \( p=(x_1,y_1) \) and \( q=(x_2,y_2) \) has center \[ (cx,cy)=\left(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2}\right)\] and radius \( r=\frac{\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}}{2} \).

For three non-collinear points \( p, q, r \), the circumcenter \( (cx,cy) \) and radius \( r \) can be computed by: \[ d=2\left(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right), \] \[ cx=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{d}, \] \[ cy=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{d} \] and \( r=\sqrt{(x_1-cx)^2+(y_1-cy)^2} \).

Your task is to output the minimum possible radius along with the corresponding circle center coordinates, each with six digits after the decimal point.

inputFormat

The first line contains two integers N and K.
Each of the following N lines contains two real numbers representing the coordinates of a point.

outputFormat

Output three real numbers: the minimum radius of a circle covering at least K points, followed by the x and y coordinates of the circle's center. Answers with an absolute error of at most \(10^{-6}\) will be accepted.

sample

1 1
0.0 0.0

0.000000 0.000000 0.000000