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