Minimum Enclosing Circle for Sensor Network

In order to ensure the safety of every member during field training, it is essential to monitor and collect information from the surrounding environment and all team members in real‐time. For this purpose, N small sensors are deployed across the training point. These sensors transmit their gathered data to a signal tower located within the training area. The signal tower has a circular receiving range and is capable of receiving signals from all of the N sensors distributed in the area (including those lying exactly on the boundary of the circle).

Since the power of the signal tower is directly proportional to the radius of its receiving range and the available power is limited (provided by pre‐stored batteries), the tower must be set up such that all sensor information is collected while minimizing the required power (i.e. the radius). Little Long has helped the instructor come up with a plan to choose both the optimal position of the tower and the smallest possible signal receiving radius. Your task is to determine the optimal signal tower placement and its corresponding minimum radius needed to cover all sensors.

The mathematical formulation of the problem is: Given a set of points \(\{(x_i,y_i)\}_{i=1}^N\), find a circle defined by center \((x,y)\) and radius \(r\) (with \(r\ge0\)) such that:

[ \begin{aligned} (x-x_i)^2+(y-y_i)^2 \le r^2 \quad \text{for all } i=1,2,\dots,N, \end{aligned} ]

and \(r\) is minimized.

inputFormat

The first line contains an integer N (\(1 \le N \le 10^5\)), the number of sensors.

Each of the following N lines contains two floating-point numbers representing the x and y coordinates of a sensor.

outputFormat

Output three floating-point numbers: the x-coordinate, y-coordinate of the optimal signal tower placement, and the minimum radius required. Each number should be printed with 6 digits after the decimal point.

sample

1
0.0 0.0

0.000000 0.000000 0.000000