eolymp
bolt
Try our new interface for solving problems
Məsələlər

Зал Круглых Столов

Зал Круглых Столов

Единственный способ попасть в Зал Круглых Столов -- пройти через Колонный Коридор. Стены Коридора изображаются на карте прямыми линиями, параллельными оси \textbf{OY} системы координат. Вход в коридор находится внизу, а выход и Коридора в Зал -- сверху. В Коридоре есть цилиндрические (на карте круглые) Колоны одинакового радиуса \textbf{R}. Напишите программу, которая по информации о размерах Коридора и розмещении Колон, определяет диаметр наибольшего из Круглых Столов, который можно пронести через такой Коридор, сохраняя поверхность Стола горизонтальной. \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}.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
0 90
3
4
10 10
70 10
50 50
10 90
Çıxış verilənləri #1
47.000
Müəllif Ilya Porublyov
Mənbə 2004 XVII All-Ukrainian Informatics Olympiad, Kharkov, March 28 - April 3, Round 2