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 and height . There are other people inside the room, and we’re given their coordinates.
We consider Alice and the people as points in the 2D plane. Alice's initial position is and she wants to move to the exit at position . 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 to .
Input
The input begins with one line containing two space-separated integers and , where is the width, and is the height of the room. The second line consists of a single integer , the number of people in the room. Then lines follow, each of them consisting of two floating-point numbers and , the coordinates of the -th person in the room.
Output
The output consists of a single value , the maximum safe distance, as a floating-point number. An additive or multiplicative error of is tolerated.
Examples
Alice can keep a distance of from every other person, and this is the best she can do. The picture below shows a possible path (in green).