eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Нійбільше порожнє коло на відрізку

Нійбільше порожнє коло на відрізку

На \textbf{2D} площині задано \textbf{N} відрізків. Необхідно знайти максимальний радіус порожнього кола з центром (\textbf{xc}, \textbf{yc}), де: \begin{itemize} \item \textbf{0} ≤ \textbf{xc} ≤ \textbf{L} \item \textbf{yc} = \textbf{0} \end{itemize} Коло вважається порожнім, якщо строго в його середині немає жодної частини відрізку (відрізок може дотикатися кола, але не перетинатися з його внутрішньою частиною). \includegraphics{https://static.e-olymp.com/content/3d/3d57fba2b797d0844f7e644c4fe187fee7ff227b.jpg} \InputFile Перший рядок містить кількість тестів \textbf{T}. Далі йде опис самих тестів. Перший рядок кожного тесту містить цілі числа \textbf{N} та \textbf{L} (\textbf{1} ≤ \textbf{N} ≤ \textbf{2000}, \textbf{0} ≤ \textbf{L} ≤ \textbf{10000}). Кожний з наступних \textbf{N} рядків містить \textbf{4} цілі числа - координати кінців відрізку: \textbf{xa}, \textbf{ya}, \textbf{xb} и \textbf{yb}. Кінці відрізку мають координати (\textbf{xa}, \textbf{ya}) та (\textbf{xb}, \textbf{yb}). Усі координати знаходяться у проміжку від \textbf{-20000} до \textbf{+20000}. Кожні два послідовні числа в одному рядку розділені одним проміжком. \OutputFile Для кожного тесту в окремому рядку вивести дійсне число \textbf{R} - максимально можливе значення радіуса порожнього кола, центр якого задовольняє заданим обмеженням. Радіус слід виводити з \textbf{3} десятковими знаками (число слід округляти вгору чи вниз згідно правил округлення).
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
1
4 10
1 1 10 3
5 3 9 1
3 1 4 1
8 3 11 -3
Вихідні дані #1
2.118