Minimum Power Base Station Placement

A wireless network base station under ideal conditions provides effective signal coverage in a circular area, and its power consumption is proportional to the square of the radius of that circle. However, with the help of a new invention – a wireless signal amplifier – the effective coverage can be stretched by a fixed amplification factor in one specific direction. With the amplifier, the base station now has an elliptical coverage area. The ellipse has a semi‐minor axis r and a semi–major axis r\( \times k \), where \( k \ge 1 \) (a given amplification factor) and the power consumption remains proportional to \( r^2 \), the square of the semi–minor axis.

Given a set of network users' positions on the plane, your task is to choose a suitable location to build the base station (i.e. decide on its center) such that all users can receive the signal while the base station's power consumption is minimized.

Note: The direction of amplification (which corresponds to the ellipse's major axis) is fixed. Without loss of generality, you may assume that the amplification is along the x–axis.

Mathematical Formulation:

After a coordinate transformation \( u = \frac{x}{k} \) and \( v = y \), the elliptical coverage region defined by the condition \[ \left(\frac{x-X}{r\cdot k}\right)^2 + \left(\frac{y-Y}{r}\right)^2 \le 1 \] becomes a circle: \[ (u-U')^2 + (v-V')^2 \le r^2, \] where \( U' = \frac{X}{k} \) and \( V' = Y \). Effectively, the problem is reduced to computing the minimum enclosing circle for the set of transformed points \( \{ (x_i/k, y_i) \} \). The goal is to determine the minimum \( r^2 \) (which is proportional to the base station's power consumption) such that a circle centered at some point covers all transformed points.

inputFormat

The first line contains two numbers: an integer n (the number of network users, where n ≥ 1) and a real number k (the amplification factor, k ≥ 1).

Each of the following n lines contains two space–separated real numbers x and y, representing the coordinates of a network user on the plane.

outputFormat

Output a single real number, the minimum possible value of \( r^2 \) needed so that an elliptical signal coverage region (with semi–minor axis \( r \) and semi–major axis \( r \times k \)) centered at an appropriate location covers all users. The answer will be accepted if it has an absolute or relative error within \( 10^{-6} \).

sample

1 2.0
0 0

0.000000