Задача №112123. Карлсон и боулинг
Как Вы уже знаете, Карлсон вернулся. Даже помог поймать жуликов.
Малыш предложил отметить это и, посовещавшись, они решили отправиться играть в боулинг. После нескольких партий Карлсон понял, что Малыш играет слишком хорошо, и что ему не победить без использования хитрости.
Сейчас, после первого броска Карлсона, на дорожке осталось n кеглей. Кегли представляют собой окружности на плоскости, не обязательно одинакового радиуса. Карлсон стоит в точке ( s x , s y ) и хочет узнать, какого минимального радиуса ему нужен шар, чтобы он мог сбить все кегли.
Шар представляет собой окружность на плоскости. При броске шара его центр находится в точке ( s x , s y ), а затем бесконечно долго двигается вдоль какого-то вектора, который Карлсон выбирает сам.
Кегля считается сбитой, если траектория шара будет иметь с кеглей хотя бы одну общую точку. После столкновения с кеглей шар не меняет направление своего движения.
У Карлсона не так много времени на бросок, помогите ему как можно быстрее!
В первой строке входного файла дано число n ( 1 ≤ n ≤ 10 5 ) — количество кегель на дорожке.
В следующих n строках входного файла дано их описание. Кегля задается тремя целыми числами x , y , r ( 1 ≤ r ≤ 10 9 ), где x , y — координаты центра кегли, r — её радиус.
В последней строке входного файла даны два целых числа s x , s y — начальные координаты Карлсона.
Все координаты по модулю не превосходят 10 9 .
В выходной файл выведите минимальный радиус шара, который нужен Карлсону, чтобы сбить все кегли.
Ответ будет считаться верным, если относительная погрешность не будет превосходить 10 - 4 .
Оценивание:
-
Первая группа тестов состоит из тестов, для которых выполняется ограничение
n
≤ 2
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
20
баллов.
-
Вторая группа тестов состоит из тестов, для которых выполняется ограничение
n
≤ 1000
. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет
40
баллов.
- Третья группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 5 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 40 баллов.
2 0 0 1 4 0 1 2 -1
0.99999999950000018000