March 28 ADA University Students + Schoolchildren
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).
Input data
The input begins with one line containing two space-separated integers x and y (1 ≤ x, y ≤ 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 ≤ n ≤ 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 ≤ x[i] ≤ x, 0 ≤ y[i] ≤ y), the coordinates of the i-th person in the room.
Output data
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
8 6 3 3 1 3 5.5 6.5 1.5
2.250000
Note
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).
