← 返回题目列表

Codeforces · 887/E

E. 小兄弟

中文机器翻译题面 查看原题

玛莎的弟弟在一张纸上画了两个点。之后,他画了一些圆圈,并将这张纸交给了他的妹妹。

玛莎刚刚从几何课回来,所以她立刻注意到了关于哥哥画画的一些有趣的事实。

首先,兄弟画的经过两点的线不与任何圆相交或接触。

此外,没有两个圆相交或接触,并且不存在一个圆位于另一个圆内部的一对圆。

此外,对于每个圆,玛莎画了一个边平行于轴的最小面积的正方形,使得该圆位于正方形内部,并注意到没有两个正方形相交或接触,并且不存在一对正方形使得一个正方形位于另一个正方形内部。

现在玛莎想要绘制尽可能最小半径的圆,使其穿过兄弟画的两个点并且不与任何其他圆相交,但其他圆可以接触玛莎的圆并且可以位于其内部。

可以保证,答案不会超过 1012。它也应该被黑客保留。

输入

第一行包含四个整数 x1, y1, x2, y2 (- 105 ≤ x1, y1, x2, y2 ≤ 105)——兄弟画的点的坐标。第一个点的坐标为 (x1, y1),第二个点的坐标为 (x2, y2)。这两点是不同的。

第二行包含单个整数 n (1 ≤ n ≤ 105) — 兄弟画的圆的数量。

接下来的 n 行包含圆的描述。每行包含三个整数 xi、yi、r​​i (- 105 ≤ xi, yi ≤ 105, 1 ≤ ri ≤ 105),描述以 (xi, yi) 为圆心、半径为 ri 的圆。

输出

输出最小实数,即可以通过给定点以不与其他圆相交的方式绘制具有该半径的圆。

如果输出的相对或绝对误差最多为 10 - 4,则输出被认为是正确的。

示例

输入 #1

2 4 7 13
3
3 0 1
12 4 2
-4 14 2

输出 #1

5.1478150705

输入 #2

-2 3 10 -10
2
7 0 3
-5 -5 2

输出 #2

9.1481831923