P2498 [SDOI2012] Save Princess Xiaoyun

The hero is about to set out to save a princess again. This time, the target to save is Princess Xiaoyun, who stands for love and justice. When the hero arrives at the entrance of the boss’s cave, he is stunned: there is not just one boss, but thousands. Upon realizing he is still level $1$, he understands this is an impossible task. But he does not give up. He wonders whether he can avoid the bosses and still save the princess. The boss’s cave can be viewed as a rectangle. The hero starts at the bottom-left corner $(1, 1)$, and the princess is at the top-right corner $(row, line)$. To avoid the bosses, the farther he stays from them, the better. Therefore, the hero decides to find a path that maximizes the minimal distance to any boss along the path. Note: The hero can move in any direction but cannot leave the rectangle. That is, he can reach any point within the rectangle (not necessarily integer coordinates). Can you help him? When the hero finds the beautiful Princess Xiaoyun, he is immediately surrounded by bosses! He gently closes his eyes, waves his hand, and with a flash of white light, uses a town portal scroll to return to the castle, but only Princess Xiaoyun goes back, because the hero forgot to step into the teleportation array.

The first line contains three integers: $n$ for the number of bosses, and $row$, $line$ for the size of the rectangle. The next $n$ lines each contain two integers, the coordinates of a boss.

Output a real number: the maximal possible minimal distance from the path to any boss, with two decimal places.

### Constraints - For $20\%$ of the testdata, boss coordinate values are $\leq 50$. - For $60\%$ of the testdata, $n \leq 1500$. - For $100\%$ of the testdata, $n \leq 3000$. Translated by ChatGPT 5