eolymp
bolt
Try our new interface for solving problems
Problems

Hall Round Table

Hall Round Table

The only way to get into the Hall Round Table - to pass through the columned corridor. Corridor walls are depicted on a map by straight lines parallel to the \textbf{OY} axis coordinate system. Log into the corridor at the bottom, and the yield and the Corridor in Hall - at the top. The corridor is cylindrical (round on the map) columns of the same radius \textbf{R}. Write a program that according to the size of the corridor and offers location Colon, determines the maximum diameter of the round tables, which can carry through such a corridor, while maintaining the horizontal surface of the table. \includegraphics{https://static.e-olymp.com/content/f7/f744393bd49a0371abb2a4930a487734a5c4b2ae.gif} \InputFile The first line contains two numbers \textbf{X_L} and \textbf{X_R} - \textbf{x}-coordinates of left and right walls of the corridor. The second line is an integer \textbf{R} (\textbf{1 }≤ \textbf{R }≤ \textbf{1000000}) - radius of Colon. The third contains an integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{200}) specifying the number of columns. Next \textbf{N} lines, each of which has two numbers - \textbf{x}-and \textbf{y}-coordinates of the center corresponding to Columns. All input coordinates are integers, not exceeding modulo \textbf{1000000}. \OutputFile Print one number - the desired maximum diameter of the Table. Diameter to remove accurate to 3 digits after the decimal point (even if it turns out to be an integer). If you can not carry a single table, then the answer should be: \textbf{0.000} The accuracy of \textbf{3} digits after the decimal point, the usual rules of rounding, this means that an answer that is displayed in the output file should be different from the exact no more than \textbf{5}×\textbf{10^\{-4\}} (ie \textbf{0.0005}). For example, if an exact answer \textbf{1.234567}, then the files should be the number \textbf{1.235}. If an exact answer \textbf{5.0005}, it is necessary to round upward, that is, the file should display \textbf{5.001}.
Time limit 1 second
Memory limit 64 MiB
Input example #1
0 90
3
4
10 10
70 10
50 50
10 90
Output example #1
47.000
Author Ilya Porublyov
Source 2004 XVII All-Ukrainian Informatics Olympiad, Kharkov, March 28 - April 3, Round 2