| Codeforces Round 444 (Div. 2) |
|---|
| Закончено |
Маленький брат Маши-умняши отметил на клетчатой бумаге две различные точки. После этого он нарисовал несколько окружностей и отдал листок сестре.
Маша только что вернулась из школы с урока по геометрии, поэтому она сразу заметила несколько особенностей на рисунке брата.
Во-первых, прямая, проходящая через точки, нарисованные братом, не пересекает ни одну из окружностей и не касается ни одной из окружностей.
Во-вторых, окружности также попарно не пересекаются, не касаются и не вкладываются.
Но Машу не просто так называют умняшей. Для каждой окружности она нарисовала квадрат со сторонами параллельными осям координат минимальной площади, что окружность полностью лежит внутри этого квадрата. Из такого рисунка Маша сразу увидела, что получившиеся квадраты также не пересекаются, не касаются и не вкладываются.
Теперь Маше-умняше стало интересно, какого минимального радиуса можно провести окружность через две точки, нарисованные братом, чтобы эта окружность не пересекала ни одной из уже нарисованных окружностей. Но уже нарисованные окружности могут быть внутри или касаться окружности, которую хочет нарисовать Маша.
Гарантируется, что ответ не превосходит 1012. Обратите внимание, что для взломов это условие также должно выполняться.
В первой строке даны четыре целых числа x1, y1, x2, y2 ( - 105 ≤ x1, y1, x2, y2 ≤ 105) — координаты точек, нарисованных братом. Первая точка имеет координаты (x1, y1), а вторая (x2, y2). Гарантируется, что точки не совпадают.
Во второй строке дано целое число n (1 ≤ n ≤ 105) — количество окружностей, нарисованных братом.
В следующих n строках записаны три целых числа xi, yi, ri ( - 105 ≤ xi, yi ≤ 105, 1 ≤ ri ≤ 105) описывающие i-ю окружность с центром в точке (xi, yi) и радиусом ri.
Выведите такое минимальное вещественное число, что возможно провести окружность через заданные точки, не пересекающие заданные окружности.
Ответ будет считаться верным, если его относительная или абсолютная ошибка не превосходит 10 - 4.
2 4 7 13
3
3 0 1
12 4 2
-4 14 2
5.1478150705
-2 3 10 -10
2
7 0 3
-5 -5 2
9.1481831923
