P2533 [AHOI2012] Signal Tower

During field training, to ensure the safety of every participant, it is very important to monitor and collect information about the surrounding environment and team members in real time. The training team deploys $N$ small sensors around the training site to collect and transmit information. These sensors communicate only with a signal tower set up within the training area. The signal tower’s reception coverage is circular; it can receive signals from all $N$ sensors distributed in the area, including those on the circle’s boundary. The tower’s power is proportional to the radius of its reception range. Because this is field training and only pre-stored battery equipment can be used, under the condition that all sensor information can be collected, the tower’s power should be minimized. Xiaolong has helped the instructor determine a placement scheme that both collects all $N$ sensors’ signals and minimizes the tower’s power. Students, can you determine how large the tower’s signal collection radius should be, and where it should be placed?

There are $N + 1$ lines. The first line contains a positive integer $N$, the number of sensors. The next $N$ lines each contain two real numbers separated by a space, which are the coordinates $x_i$ and $y_i$ of the $i$-th sensor ($x_i, y_i$ are within the range of double precision).

One line containing three real numbers separated by spaces: the coordinates of the signal tower and the tower’s coverage radius.

- Determine that a sensor lies on the boundary if the absolute value of the difference between its distance to the circle center and the tower’s reception radius is less than $10^{-6}$. Keep the final result to $2$ decimal places. - Constraints: - For $30\%$ of the testdata, $1 \le N \le 10^4$. - For $70\%$ of the testdata, $1 \le N \le 2 \times 10^4$. - For $100\%$ of the testdata, $1 \le N \le 10^6$. - This problem contains hack testdata and is scored as $0$ points. Translated by ChatGPT 5