409390: GYM103496 C Caught in Candy

C. Caught in Candytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Bob wants to give Cindy a gift for Valentine's Day. Whereas others would buy storebought sweets to give to others, Bob thinks that his gift will have a greater impact if it is homemade. Bob learned that one of Cindy's favorite foods is pili nut brittle (from Camarines Sur). Even though he doesn't know how to make it, he's going to try his best! All he needs is a YouTube tutorial and a dream.

First, Bob scatters $$$n$$$ pili nuts on a silicone mat. The position of the $$$i$$$th nut can represented as an ordered pair $$$(x_i, y_i)$$$, using the standard Cartesian coordinate system (for simplicity, we model each nut as just a single point). It is possible to have multiple nuts at the same location. Then, Bob pours a molten mixture of corn syrup and sugar at the point $$$(h,k)$$$. The hot liquid flows out evenly in all directions, so we can model the liquid as a circle centered at $$$(h,k)$$$, initially of radius $$$0$$$, and whose radius grows at a rate of $$$1$$$ unit per second.

Bob will stop pouring the very instant that all pili nuts are within the hot liquid, i.e. when all points are on or within the circle. Once the mixture cools and solidifies, Bob will be left with a circular piece of pili nut brittle. What will be the diameter of this final product?

Input

The first line of input contains three space-separated integers $$$n$$$, $$$h$$$, and $$$k$$$.

Then, $$$n$$$ lines of input follow, each containing two space-separated integers $$$x_i$$$ and $$$y_i$$$, corresponding to the location of the $$$i$$$th pili nut.

Output

Output the diameter of the final circle of pili nut brittle. Your answer will be considered correct if it is within $$$10^{-3}$$$ of the correct answer.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline -1000 \leq h, k \leq 1000 \\ -1000 \leq x_i, y_i \leq 1000 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{25} & n=1 \\ \hline 2 & \mathbf{25} & 1 \leq n \leq 5 \\ \hline 3 & \mathbf{25} & 1 \leq n \leq 500 \\ \hline 4 & \mathbf{25} & 1 \leq n \leq 10^5 \\ \hline \end{array}\\

\end{align*}$$$$$$

ExamplesInput

1 2 3
2 4

Output

2.000000000000

Input

4 0 0
-3 4
5 0
1 1
-4 -3

Output

10.000000000000

Input

2 1 1
0 0
2 0

Output

2.828427124746

Note

We illustrate the second sample input. If the molten sugar is to be poured at $$$(0,0)$$$, then here is the layout of the liquid and the pili nuts.

We can show that after $$$5$$$ seconds have passed, all nuts are on or within the circle (recall that we model the pili nuts as just points). At this time, the brittle has a diameter of $$$10$$$ units.