eolymp
bolt
Try our new interface for solving problems
Problems

Safe Distance

Safe Distance

The past year has been difficult, with a virus spreading among the population. Fortunately, Alice knows that one of the keys to be healthy is to keep a safe distance from other people. Alice is currently in a closed room, represented in the 2D plane, with width $x$ and height $y$. There are $n$ other people inside the room, and we’re given their $(x_i, y_i)$ coordinates. We consider Alice and the $n$ people as points in the 2D plane. Alice's initial position is $(0, 0)$ and she wants to move to the exit at position $(x, y)$. She can move freely in any direction inside the room, but can not step outside the room bounds. Find the maximum distance Alice can keep from other people while moving from $(0, 0)$ to $(x, y)$. \InputFile The input begins with one line containing two space-separated integers $x$ and $y~(1 \le x, y \le 10^6)$, where $x$ is the width, and $y$ is the height of the room. The second line consists of a single integer $n~(1 \le n \le 1000)$, the number of people in the room. Then $n$ lines follow, each of them consisting of two floating-point numbers $x_i$ and $y_i~(0 \le x_i \le x, 0 \le y_i \le y)$, the coordinates of the $i$-th person in the room. \OutputFile The output consists of a single value $d$, the maximum safe distance, as a floating-point number. An additive or multiplicative error of $10^{-5}$ is tolerated. \Examples Alice can keep a distance of $2.25$ from every other person, and this is the best she can do. The picture below shows a possible path (in green). \includegraphics{https://static.eolymp.com/content/7g/7gjj8tqe4t0nl2llgo2k4ldiu0.gif}
Time limit 2 seconds
Memory limit 128 MiB
Input example #1
8 6
3
3 1
3 5.5
6.5 1.5
Output example #1
2.250000
Source 2021 ACM Southwestern Europe Regional Contest (SWERC), Paris, March 7, Problem C