{"raw_statement":[{"iden":"statement","content":"Masha's little brother draw two points on a sheet of paper. After that, he draws some circles and gave the sheet to his sister.\n\nMasha has just returned from geometry lesson so she instantly noticed some interesting facts about brother's drawing.\n\nAt first, the line going through two points, that brother drew, doesn't intersect or touch any circle.\n\nAlso, no two circles intersect or touch, and there is no pair of circles such that one circle is located inside another.\n\nMoreover, for each circle, Masha drew a square of the minimal area with sides parallel axis such that this circle is located inside the square and noticed that there is no two squares intersect or touch and there is no pair of squares such that one square is located inside other.\n\nNow Masha wants to draw circle of minimal possible radius such that it goes through two points that brother drew and doesn't intersect any other circle, but other circles can touch Masha's circle and can be located inside it.\n\n**It's guaranteed, that answer won't exceed 1012. It should be held for hacks as well.**"},{"iden":"input","content":"First line contains four integers _x_1, _y_1, _x_2, _y_2 ( - 105 ≤ _x_1, _y_1, _x_2, _y_2 ≤ 105) — coordinates of points that brother drew. First point has coordinates (_x_1, _y_1) and second point has coordinates (_x_2, _y_2). These two points are different.\n\nThe second line contains single integer _n_ (1 ≤ _n_ ≤ 105) — the number of circles that brother drew.\n\nNext _n_ lines contains descriptions of circles. Each line contains three integers _x__i_, _y__i_, _r__i_ ( - 105 ≤ _x__i_, _y__i_ ≤ 105, 1 ≤ _r__i_ ≤ 105) describing circle with center (_x__i_, _y__i_) and radius _r__i_."},{"iden":"output","content":"Output smallest real number, that it's possible to draw a circle with such radius through given points in such a way that it doesn't intersect other circles.\n\nThe output is considered correct if it has a relative or absolute error of at most 10 - 4."},{"iden":"examples","content":"Input\n\n2 4 7 13\n3\n3 0 1\n12 4 2\n-4 14 2\n\nOutput\n\n5.1478150705\n\nInput\n\n\\-2 3 10 -10\n2\n7 0 3\n-5 -5 2\n\nOutput\n\n9.1481831923"},{"iden":"note","content":"![image](https://espresso.codeforces.com/f1db1fc4281dd758ba03a166023183c93ff3e868.png) ![image](https://espresso.codeforces.com/471cd0817c36008969a2fb49001b32799f1c2a4c.png)"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"Masha 的小弟弟在一张纸上画了两个点。之后，他又画了一些圆，并把纸给了姐姐。\\n\\nMasha 刚上完几何课，立刻注意到了弟弟画图的一些有趣性质：\\n\\n首先，经过这两个点的直线不与任何圆相交或相切。\\n\\n此外，任意两个圆互不相交、互不相切，且不存在一对圆，使得其中一个完全位于另一个内部。\\n\\n此外，对于每个圆，Masha 画了一个边与坐标轴平行的最小面积正方形，使得该圆完全位于该正方形内，并注意到任意两个正方形互不相交、互不相切，且不存在一对正方形，使得其中一个完全位于另一个内部。\\n\\n现在，Masha 希望画一个半径尽可能小的圆，使其经过弟弟画的两个点，且不与任何其他圆相交（但其他圆可以与 Masha 的圆相切，也可以位于其内部）。\\n\\n*保证答案不超过 #cf_span[1012]。该限制同样适用于 Hack。*\\n\\n第一行包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[ - 105 ≤ x1, y1, x2, y2 ≤ 105]) —— 弟弟画的两个点的坐标。第一个点坐标为 (#cf_span[x1], #cf_span[y1])，第二个点坐标为 (#cf_span[x2], #cf_span[y2])。这两个点互不相同。\\n\\n第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 弟弟画的圆的数量。\\n\\n接下来 #cf_span[n] 行，每行描述一个圆。每行包含三个整数 #cf_span[xi], #cf_span[yi], #cf_span[ri] (#cf_span[ - 105 ≤ xi, yi ≤ 105], #cf_span[1 ≤ ri ≤ 105])，描述一个以 (#cf_span[xi], #cf_span[yi]) 为圆心、半径为 #cf_span[ri] 的圆。\\n\\n请输出一个最小的实数，表示存在一个经过给定两点、且不与任何其他圆相交的圆的半径。\\n\\n输出的相对误差或绝对误差不超过 #cf_span[10 - 4] 即视为正确。\\n\\n \"},{\"iden\":\"input\",\"content\":\"第一行包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[ - 105 ≤ x1, y1, x2, y2 ≤ 105]) —— 弟弟画的两个点的坐标。第一个点坐标为 (#cf_span[x1], #cf_span[y1])，第二个点坐标为 (#cf_span[x2], #cf_span[y2])。这两个点互不相同。第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 弟弟画的圆的数量。接下来 #cf_span[n] 行，每行描述一个圆。每行包含三个整数 #cf_span[xi], #cf_span[yi], #cf_span[ri] (#cf_span[ - 105 ≤ xi, yi ≤ 105], #cf_span[1 ≤ ri ≤ 105])，描述一个以 (#cf_span[xi], #cf_span[yi]) 为圆心、半径为 #cf_span[ri] 的圆。\"},{\"iden\":\"output\",\"content\":\"请输出一个最小的实数，表示存在一个经过给定两点、且不与任何其他圆相交的圆的半径。输出的相对误差或绝对误差不超过 #cf_span[10 - 4] 即视为正确。\"},{\"iden\":\"examples\",\"content\":\"输入\\n2 4 7 13\\n3\\n3 0 1\\n12 4 2\\n-4 14 2\\n输出\\n5.1478150705\\n\\n输入\\n-2 3 10 -10\\n2\\n7 0 3\\n-5 -5 2\\n输出\\n9.1481831923\"},{\"iden\":\"note\",\"content\":\" \"}]\n\n{\"problem_iden\":\"CF887E\",\"statement_source\":\"Codeforces\",\"problem_source\":\"CF\",\"problem_statements\":[{\"iden\":\"statement\",\"content\":\"Masha 的小弟弟在一张纸上画了两个点。之后，他又画了一些圆，并把纸给了姐姐。\\n\\nMasha 刚上完几何课，立刻注意到了弟弟画图的一些有趣性质：\\n\\n首先，经过这两个点的直线不与任何圆相交或相切。\\n\\n此外，任意两个圆互不相交、互不相切，且不存在一对圆，使得其中一个完全位于另一个内部。\\n\\n此外，对于每个圆，Masha 画了一个边与坐标轴平行的最小面积正方形，使得该圆完全位于该正方形内，并注意到任意两个正方形互不相交、互不相切，且不存在一对正方形，使得其中一个完全位于另一个内部。\\n\\n现在，Masha 希望画一个半径尽可能小的圆，使其经过弟弟画的两个点，且不与任何其他圆相交（但其他圆可以与 Masha 的圆相切，也可以位于其内部）。\\n\\n*保证答案不超过 #cf_span[1012]。该限制同样适用于 Hack。*\\n\\n第一行包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[ - 105 ≤ x1, y1, x2, y2 ≤ 105]) —— 弟弟画的两个点的坐标。第一个点坐标为 (#cf_span[x1], #cf_span[y1])，第二个点坐标为 (#cf_span[x2], #cf_span[y2])。这两个点互不相同。\\n\\n第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 弟弟画的圆的数量。\\n\\n接下来 #cf_span[n] 行，每行描述一个圆。每行包含三个整数 #cf_span[xi], #cf_span[yi], #cf_span[ri] (#cf_span[ - 105 ≤ xi, yi ≤ 105], #cf_span[1 ≤ ri ≤ 105])，描述一个以 (#cf_span[xi], #cf_span[yi]) 为圆心、半径为 #cf_span[ri] 的圆。\\n\\n请输出一个最小的实数，表示存在一个经过给定两点、且不与任何其他圆相交的圆的半径。\\n\\n输出的相对误差或绝对误差不超过 #cf_span[10 - 4] 即视为正确。\\n\\n \"},{\"iden\":\"input\",\"content\":\"第一行包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[ - 105 ≤ x1, y1, x2, y2 ≤ 105]) —— 弟弟画的两个点的坐标。第一个点坐标为 (#cf_span[x1], #cf_span[y1])，第二个点坐标为 (#cf_span[x2], #cf_span[y2])。这两个点互不相同。第二行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 弟弟画的圆的数量。接下来 #cf_span[n] 行，每行描述一个圆。每行包含三个整数 #cf_span[xi], #cf_span[yi], #cf_span[ri] (#cf_span[ - 105 ≤ xi, yi ≤ 105], #cf_span[1 ≤ ri ≤ 105])，描述一个以 (#cf_span[xi], #cf_span[yi]) 为圆心、半径为 #cf_span[ri] 的圆。\"},{\"iden\":\"output\",\"content\":\"请输出一个最小的实数，表示存在一个经过给定两点、且不与任何其他圆相交的圆的半径。输出的相对误差或绝对误差不超过 #cf_span[10 - 4] 即视为正确。\"},{\"iden\":\"examples\",\"content\":\"输入\\n2 4 7 13\\n3\\n3 0 1\\n12 4 2\\n-4 14 2\\n输出\\n5.1478150705\\n\\n输入\\n-2 3 10 -10\\n2\\n7 0 3\\n-5 -5 2\\n输出\\n9.1481831923\"},{\"iden\":\"note\",\"content\":\" \"}],\"time_limit\":3000,\"memory_limit\":524288}","sample_group":[],"show_order":[],"formal_statement":"Let $ P_1 = (x_1, y_1) $, $ P_2 = (x_2, y_2) $ be two distinct points.  \nLet $ C_i = (x_i, y_i, r_i) $, for $ i = 1, 2, \\dots, n $, be $ n $ given circles with centers $ (x_i, y_i) $ and radii $ r_i $.\n\nDefine $ d = \\|P_1 - P_2\\| $, the Euclidean distance between $ P_1 $ and $ P_2 $.\n\nLet $ \\mathcal{C} $ be the set of all circles passing through $ P_1 $ and $ P_2 $.  \nEach such circle has its center lying on the perpendicular bisector of segment $ P_1P_2 $.  \nLet $ M = \\left( \\frac{x_1 + x_2}{2}, \\frac{y_1 + y_2}{2} \\right) $ be the midpoint of $ P_1P_2 $, and let $ \\vec{v} = (x_2 - x_1, y_2 - y_1) $ be the direction vector of $ P_1P_2 $.  \nThen the perpendicular bisector is the line through $ M $ perpendicular to $ \\vec{v} $.\n\nFor any circle in $ \\mathcal{C} $ with center $ O = (x, y) $ on the perpendicular bisector, its radius is $ R = \\|O - P_1\\| $.\n\nWe seek the **minimum** $ R > 0 $ such that:\n\n- The circle centered at $ O $ with radius $ R $ passes through $ P_1 $ and $ P_2 $,\n- For all $ i \\in \\{1, \\dots, n\\} $, the circle $ (O, R) $ does **not intersect** the circle $ C_i $, i.e.,  \n  $$\n  \\|O - (x_i, y_i)\\| \\geq R + r_i \\quad \\text{(external non-intersection)} \\quad \\text{or} \\quad \\|O - (x_i, y_i)\\| \\leq |R - r_i| \\quad \\text{(one inside the other)}.\n  $$\n\nBut the problem **allows** other circles to **touch** or be **inside** Masha’s circle.  \nSo the **only forbidden** configuration is **intersection** (i.e., strict overlap without containment).  \nThus, the constraint for each $ i $ is:\n$$\n\\|O - (x_i, y_i)\\| \\geq R + r_i \\quad \\text{or} \\quad \\|O - (x_i, y_i)\\| \\leq R - r_i \\quad \\text{(if } R \\geq r_i\\text{)}.\n$$\n\nBut note: since Masha’s circle must pass through $ P_1 $ and $ P_2 $, and the line $ P_1P_2 $ does not intersect or touch any existing circle, and no circle contains another or touches another, and the minimal axis-aligned squares of the circles do not intersect or contain each other, we are guaranteed that **no existing circle contains both $ P_1 $ and $ P_2 $**.\n\nMoreover, the problem asks for the **minimal possible radius** $ R $, so we are looking for the **smallest** $ R $ such that the circle through $ P_1, P_2 $ with center on the perpendicular bisector avoids intersecting any $ C_i $.\n\nThe **critical constraint** is that for each circle $ C_i $, we must have:\n$$\n\\|O - C_i\\| \\geq R + r_i \\quad \\text{or} \\quad \\|O - C_i\\| \\leq R - r_i.\n$$\n\nBut since we want **minimal** $ R $, and $ R \\geq \\frac{d}{2} $ (the minimal possible radius for a circle through $ P_1, P_2 $ is when the center is at $ M $, giving $ R = d/2 $), and increasing $ R $ moves the center away from $ M $ along the perpendicular bisector, we consider the following:\n\nLet $ h $ be the signed distance from $ M $ to $ O $ along the perpendicular bisector. Then:\n$$\nR = \\sqrt{ \\left( \\frac{d}{2} \\right)^2 + h^2 }.\n$$\n\nFor each existing circle $ C_i $, the distance from $ O $ to $ C_i $ is:\n$$\n\\|O - C_i\\| = \\sqrt{ (x_i - m_x)^2 + (y_i - m_y + h \\cdot \\hat{n}_y)^2 } \\quad \\text{(depending on direction of bisector)}\n$$\n\nBut we can simplify: for each $ C_i $, the minimal possible $ R $ such that the circle through $ P_1, P_2 $ avoids intersecting $ C_i $ is determined by the **tangent condition**.\n\nFor each circle $ C_i $, the **smallest** circle through $ P_1, P_2 $ that is **externally tangent** to $ C_i $ has radius $ R_i $ satisfying:\n$$\n\\|O - C_i\\| = R_i + r_i\n$$\nand $ O $ lies on the perpendicular bisector.\n\nAlternatively, the circle through $ P_1, P_2 $ may be **internally tangent** to $ C_i $, i.e., $ C_i $ contains the new circle and they touch: $ \\|O - C_i\\| = r_i - R_i $, but this requires $ r_i \\geq R_i $, and since we are minimizing $ R $, and $ R_i $ is small, this may not be feasible unless $ C_i $ is large and close.\n\nBut note: the problem says **\"other circles can touch Masha's circle and can be located inside it\"**, so **both** external tangency and internal tangency (with containment) are allowed.  \nThe **only forbidden** is **intersection without containment**.\n\nSo for each $ C_i $, the **forbidden** region for $ O $ is the set of centers such that:\n$$\n|R - r_i| < \\|O - C_i\\| < R + r_i\n$$\n\nWe want the **smallest** $ R \\geq \\frac{d}{2} $ such that there exists a center $ O $ on the perpendicular bisector with $ \\|O - P_1\\| = R $, and for all $ i $, $ \\|O - C_i\\| \\geq R + r_i $ or $ \\|O - C_i\\| \\leq R - r_i $.\n\nSince $ R \\geq \\frac{d}{2} $, and we want the **minimum** such $ R $, we can consider the **critical values** of $ R $ where the circle through $ P_1, P_2 $ becomes tangent (externally or internally) to one of the $ C_i $.\n\nThus, the minimal valid $ R $ is the **minimum** over:\n\n- $ R_0 = \\frac{d}{2} $, if the circle with diameter $ P_1P_2 $ does not intersect any $ C_i $ (i.e., for all $ i $, either $ \\|M - C_i\\| \\geq \\frac{d}{2} + r_i $ or $ \\|M - C_i\\| \\leq \\frac{d}{2} - r_i $),\n- Or, the **smallest** $ R > \\frac{d}{2} $ such that for some $ i $, the circle through $ P_1, P_2 $ with center on the perpendicular bisector is **externally tangent** to $ C_i $, i.e.,  \n  $$\n  \\|O - C_i\\| = R + r_i\n  $$\n  and $ O $ lies on the perpendicular bisector.\n\nWe can compute for each circle $ C_i $, the minimal $ R $ such that a circle through $ P_1, P_2 $ is externally tangent to $ C_i $.  \nThis is a classical geometric problem: find the circle through two points tangent to a third circle.\n\nThe set of centers $ O $ of circles through $ P_1, P_2 $ is the perpendicular bisector.  \nThe condition $ \\|O - C_i\\| = R + r_i $ and $ R = \\|O - P_1\\| $ gives:\n$$\n\\|O - C_i\\| = \\|O - P_1\\| + r_i\n$$\n\nThis is the definition of a **hyperbola** with foci $ C_i $ and $ P_1 $, and constant difference $ r_i $.  \nBut since $ O $ lies on a line (the perpendicular bisector), the intersection of this hyperbola with the line gives the possible centers.\n\nAlternatively, we can solve numerically: for each $ C_i $, we can compute the minimal $ R $ such that there exists $ O $ on the perpendicular bisector with $ \\|O - P_1\\| = R $ and $ \\|O - C_i\\| = R + r_i $.\n\nDefine $ f(h) = \\|O(h) - C_i\\| - \\|O(h) - P_1\\| $, where $ O(h) $ is the point on the perpendicular bisector at signed distance $ h $ from $ M $.  \nWe want $ f(h) = r_i $.\n\nBut note: $ \\|O(h) - P_1\\| = \\sqrt{ (d/2)^2 + h^2 } = R(h) $,  \nand $ \\|O(h) - C_i\\| = \\sqrt{ (x_i - m_x)^2 + (y_i - m_y + h \\cdot \\hat{n}_y)^2 } $ — actually, we need to define the direction.\n\nLet $ \\vec{n} $ be a unit vector perpendicular to $ \\vec{v} = (x_2 - x_1, y_2 - y_1) $.  \nThen $ O(h) = M + h \\vec{n} $.\n\nThen:\n$$\nR(h) = \\sqrt{ \\left( \\frac{d}{2} \\right)^2 + h^2 }\n$$\n$$\nD_i(h) = \\| O(h) - C_i \\| = \\sqrt{ (m_x + h n_x - x_i)^2 + (m_y + h n_y - y_i)^2 }\n$$\n\nWe want:\n$$\nD_i(h) = R(h) + r_i\n$$\n\nThis is a nonlinear equation in $ h $.  \nWe can solve it numerically, but note: we are looking for the **smallest** $ R $, so we want the **smallest** $ h \\geq 0 $ (by symmetry, we can consider $ h \\geq 0 $) such that for some $ i $, $ D_i(h) = R(h) + r_i $, or $ D_i(h) = |R(h) - r_i| $ (for internal tangency).\n\nBut for internal tangency: $ D_i(h) = |R(h) - r_i| $.  \nSince $ R(h) \\geq d/2 $, and $ r_i \\geq 1 $, if $ R(h) \\geq r_i $, then $ D_i(h) = R(h) - r_i $.  \nThis would mean the circle $ C_i $ contains the new circle and they touch.\n\nSo for each $ C_i $, we have **two** candidate equations:\n\n1. **External tangency**: $ D_i(h) = R(h) + r_i $\n2. **Internal tangency**: $ D_i(h) = R(h) - r_i $, provided $ R(h) \\geq r_i $\n\nWe solve each equation for $ h \\geq 0 $, compute the corresponding $ R(h) $, and take the **minimum** over all valid solutions and $ R_0 = d/2 $ (if feasible).\n\nBut note: the problem guarantees that the line $ P_1P_2 $ does not intersect or touch any circle, so at $ h = 0 $, the circle with diameter $ P_1P_2 $ does not intersect any $ C_i $.  \nWe must check if it satisfies the non-intersection condition.\n\nFor $ h = 0 $, $ R = d/2 $, $ O = M $.  \nFor each $ i $, check:\n- If $ \\|M - C_i\\| \\geq \\frac{d}{2} + r_i $ → OK (external)\n- If $ \\|M - C_i\\| \\leq \\frac{d}{2} - r_i $ → OK (internal, containment)\n- If $ \\left| \\frac{d}{2} - r_i \\right| < \\|M - C_i\\| < \\frac{d}{2} + r_i $ → **INTERSECTION** → not allowed.\n\nSo if for all $ i $, the condition holds at $ h = 0 $, then answer is $ d/2 $.\n\nOtherwise, we must find the smallest $ h > 0 $ such that for some $ i $, $ D_i(h) = R(h) + r_i $ or $ D_i(h) = R(h) - r_i $, and for all other $ j \\neq i $, the circle at $ O(h) $ does not intersect $ C_j $.\n\nBut note: as $ h $ increases, $ R(h) $ increases, and the center moves away from $ M $.  \nThe function $ D_i(h) - R(h) $ is continuous and typically increases (since the center moves away from $ C_i $ in some direction), so the equation $ D_i(h) = R(h) + r_i $ will have a unique solution for each $ i $ (if any), and similarly for internal tangency.\n\nBut we are to find the **minimum** $ R $ such that **all** constraints are satisfied.  \nSo the minimal valid $ R $ is the **minimum** over:\n\n- $ R_0 = d/2 $, if feasible,\n- For each $ i $, the **smallest** $ R_i^{\\text{ext}} > d/2 $ such that the circle is externally tangent to $ C_i $,\n- For each $ i $, the **smallest** $ R_i^{\\text{int}} \\geq r_i $ such that the circle is internally tangent to $ C_i $ (i.e., $ C_i $ contains it and they touch).\n\nThen take the **minimum** among all these candidate $ R $ values, and verify that for that $ R $, **all** other circles are also non-intersecting.\n\nBut note: the minimal such $ R $ will be determined by the **first** circle that becomes tangent as we increase $ R $ from $ d/2 $.  \nSo we can compute for each $ i $ the minimal $ R $ at which tangency occurs with $ C_i $, and then take the **minimum** of these values, and check if at that $ R $, no other circle is intersected.\n\nSince the constraints are independent and the function is monotonic in $ h $, the **global minimum** valid $ R $ is the **minimum** over all the tangency radii from all circles.\n\nThus, the algorithm is:\n\n1. Compute $ d = \\|P_1 - P_2\\| $, $ R_0 = d/2 $, $ M = \\text{midpoint} $.\n2. For each circle $ C_i $, check if at $ R_0 $, the circle centered at $ M $ with radius $ R_0 $ satisfies:\n   $$\n   \\|M - C_i\\| \\geq R_0 + r_i \\quad \\text{or} \\quad \\|M - C_i\\| \\leq R_0 - r_i\n   $$\n   If **all** satisfy, return $ R_0 $.\n3. Otherwise, for each circle $ C_i $, compute the smallest $ R > R_0 $ such that a circle through $ P_1, P_2 $ with center on the perpendicular bisector is tangent to $ C_i $ (either externally or internally).\n   - For external tangency: solve $ \\|O - C_i\\| = R + r_i $, with $ R = \\sqrt{(d/2)^2 + h^2} $, $ O = M + h \\vec{n} $.\n   - For internal tangency: solve $ \\|O - C_i\\| = R - r_i $, with $ R \\geq r_i $.\n4. For each such solution $ R $, verify that for **all** other circles $ C_j $, $ j \\neq i $, the circle with center $ O $ and radius $ R $ does not intersect $ C_j $ (i.e., satisfies the non-intersection condition).\n5. Among all such valid $ R $ from all circles and all tangency types, take the **minimum**.\n\nBut note: the problem size is $ n \\leq 10^5 $, so we cannot check all $ O(h) $ for all $ i $.\n\nHowever, the minimal $ R $ must be the **smallest** tangency radius among all $ C_i $, because as we increase $ R $ from $ R_0 $, the first circle we hit (i.e., the one requiring the smallest $ R $ to become tangent) will be the bottleneck.\n\nMoreover, since the set of forbidden $ R $ is a union of intervals, the minimal allowed $ R $ is the minimal value where the circle becomes tangent to some $ C_i $.\n\nSo we can:\n\n- For each $ i $, compute the **minimal** $ R_i $ (from external and internal tangency) such that tangency occurs with $ C_i $.\n- Let $ R^* = \\min_i R_i $\n- Then check if at $ R^* $, with the corresponding center $ O^* $, the circle does not intersect any other $ C_j $.\n\nBut due to the geometric constraints (no two circles intersect or touch, no containment, and squares don't intersect or contain), and the fact that the line $ P_1P_2 $ is far from all circles, it is highly likely that the **first** tangency encountered is the global minimum, and no other circle is intersected at that radius.\n\nThus, the answer is:\n$$\n\\boxed{ \\min \\left( \\frac{d}{2}, \\min_{i=1}^{n} \\left\\{ \\min \\left( R_i^{\\text{ext}}, R_i^{\\text{int}} \\right) \\right\\} \\right) }\n$$\nwhere $ R_i^{\\text{ext}} $ and $ R_i^{\\text{int}} $ are the minimal radii for external and internal tangency with $ C_i $, computed as described, and only if feasible.\n\nBut we must compute $ R_i^{\\text{ext}} $ and $ R_i^{\\text{int}} $.\n\nLet $ \\vec{v} = (x_2 - x_1, y_2 - y_1) $, $ d = \\|\\vec{v}\\| $, $ M = \\left( \\frac{x_1+x_2}{2}, \\frac{y_1+y_2}{2} \\right) $.\n\nLet $ \\vec{n} = \\left( -\\frac{v_y}{d}, \\frac{v_x}{d} \\right) $ be a unit perpendicular vector.\n\nThen for a point $ O(h) = M + h \\vec{n} $, $ h \\in \\mathbb{R} $, the radius is $ R(h) = \\sqrt{ (d/2)^2 + h^2 } $.\n\nLet $ \\vec{c_i} = (x_i, y_i) $, $ \\vec{m} = M $.\n\nThen:\n$$\nD_i(h) = \\| \\vec{c_i} - \\vec{m} - h \\vec{n} \\| = \\sqrt{ \\| \\vec{c_i} - \\vec{m} \\|^2 - 2 h \\vec{n} \\cdot (\\vec{c_i} - \\vec{m}) + h^2 }\n$$\n\nLet $ a_i = \\| \\vec{c_i} - \\vec{m} \\| $, $ b_i = \\vec{n} \\cdot (\\vec{c_i} - \\vec{m}) $.\n\nThen:\n$$\nD_i(h) = \\sqrt{ a_i^2 - 2 b_i h + h^2 }\n$$\n\n**External tangency condition**:\n$$\n\\sqrt{ a_i^2 - 2 b_i h + h^2 } = \\sqrt{ (d/2)^2 + h^2 } + r_i\n$$\n\nLet $ R(h) = \\sqrt{ (d/2)^2 + h^2 } $, so:\n$$\n\\sqrt{ a_i^2 - 2 b_i h + h^2 } = R(h) + r_i\n$$\n\nSquare both sides:\n$$\na_i^2 - 2 b_i h + h^2 = R(h)^2 + 2 r_i R(h) + r_i^2 = \\left( \\frac{d^2}{4} + h^2 \\right) + 2 r_i R(h) + r_i^2\n$$\n\nSimplify:\n$$\na_i^2 - 2 b_i h = \\frac{d^2}{4} + 2 r_i R(h) + r_i^2\n$$\n\nBring all to one side:\n$$\na_i^2 - \\frac{d^2}{4} - r_i^2 - 2 b_i h = 2 r_i R(h)\n$$\n\nLet $ K_i = a_i^2 - \\frac{d^2}{4} - r_i^2 $, then:\n$$\nK_i - 2 b_i h = 2 r_i \\sqrt{ \\frac{d^2}{4} + h^2 }\n$$\n\nNow square both sides again:\n$$\n(K_i - 2 b_i h)^2 = 4 r_i^2 \\left( \\frac{d^2}{4} + h^2 \\right)\n$$\n\nThis is a quadratic in $ h $:\n$$\nK_i^2 - 4 K_i b_i h + 4 b_i^2 h^2 = r_i^2 d^2 + 4 r_i^2 h^2\n$$\n\nBring all to left:\n$$\n(4 b_i^2 - 4 r_i^2) h^2 - 4 K_i b_i h + (K_i^2 - r_i^2 d^2) = 0\n$$\n\nSolve this quadratic for $ h $.  \nTake the **smallest positive** $ h $ that satisfies the original equation (since squaring introduces extraneous roots).\n\nSimilarly, for **internal tangency**:\n$$\n\\sqrt{ a_i^2 - 2 b_i h + h^2 } = \\left| \\sqrt{ \\frac{d^2}{4} + h^2 } - r_i \\right|\n$$\n\nSince $ R(h) \\geq d/2 > 0 $, and we want $ R(h) \\geq r_i $ for containment, assume $ R(h) \\geq r_i $, then:\n$$\n\\sqrt{ a_i^2 - 2 b_i h + h^2 } = R(h) - r_i\n$$\n\nSquare:\n$$\na_i^2 - 2 b_i h + h^2 = R(h)^2 - 2 r_i R(h) + r_i^2 = \\frac{d^2}{4} + h^2 - 2 r_i R(h) + r_i^2\n$$\n\nSimplify:\n$$\na_i^2 - 2 b_i h = \\frac{d^2}{4} - 2 r_i R(h) + r_i^2\n$$\n\nThen:\n$$\nK_i - 2 b_i h = -2 r_i R(h)\n$$\n\nWhere $ K_i = a_i^2 - \\frac{d^2}{4} - r_i^2 $ as before.\n\nSo:\n$$\nK_i - 2 b_i h = -2 r_i \\sqrt{ \\frac{d^2}{4} + h^2 }\n$$\n\nSquare both sides:\n$$\n(K_i - 2 b_i h)^2 = 4 r_i^2 \\left( \\frac{d^2}{4} + h^2 \\right)\n$$\n\nSame equation as external tangency!\n\nSo both external and internal tangency lead to the **same quadratic**:\n$$\n(4 b_i^2 - 4 r_i^2) h^2 - 4 K_i b_i h + (K_i^2 - r_i^2 d^2) = 0\n$$\n\nBut we must **check** which solutions satisfy the original equation.\n\nSo for each circle $ C_i $, solve the quadratic for $ h $, then for each real root $ h $, compute $ R = \\sqrt{(d/2)^2 + h^2} $, and check:\n\n- If $ D_i(h) = R + r_i $ → external tangency → valid\n- If $ D_i(h) = |R - r_i| $ and $ R \\geq r_i $ → internal tangency → valid\n\nThen collect all valid $ R $ from all circles.\n\nThe answer is the **minimum** among:\n\n- $ R_0 = d/2 $, if feasible (i.e., for all $ i $, $ \\|M - C_i\\| \\geq R_0 + r_i $ or $ \\|M - C_i\\| \\leq R_0 - r_i $),\n- All valid $ R $ from tangency conditions above.\n\nWe output this minimum.\n\nNote: We must be cautious with numerical precision, but the problem allows error $ 10^{-4} $.\n\nThus, the formal mathematical representation is:\n\n---\n\n**Definitions:**\n\nLet $ P_1 = (x_1, y_1) $, $ P_2 = (x_2, y_2) $, $ d = \\|P_1 - P_2\\| $, $ M = \\left( \\frac{x_1 + x_2}{2}, \\frac{y_1 + y_2}{2} \\right) $.  \nLet $ \\vec{v} = (x_2 - x_1, y_2 - y_1) $, $ \\vec{n} = \\left( -\\frac{v_y}{d}, \\frac{v_x}{d} \\right) $.  \nFor each circle $ i $, let $ C_i = (x_i, y_i, r_i) $, $ \\vec{c_i} = (x_i, y_i) $,  \n$ a_i = \\| \\vec{c_i} - M \\| $, $ b_i = \\vec{n} \\cdot (\\vec{c_i} - M) $,  \n$ K_i = a_i^2 - \\frac{d^2}{4} - r_i^2 $.\n\n**Constraints:**\n\n- $ R_0 = \\frac{d}{2} $ is feasible if for all $ i $, $ a_i \\geq R_0 + r_i $ or $ a_i \\leq R_0 - r_i $.\n\n**Objective:**\n\nFind the minimum $ R \\geq R_0 $ such that there exists $ h \\in \\mathbb{R} $ with $ R = \\sqrt{ \\left( \\frac{d}{2} \\right)^2 + h^2 } $, and for all $ i $,  \n$$\n\\| M + h \\vec{n} - C_i \\| \\geq R + r_i \\quad \\text{or} \\quad \\| M + h \\vec{n} - C_i \\| \\leq |R - r_i|.\n$$\n\n**Solution:**\n\nCompute $ R_{\\text{min}} = \\min \\left( R_0 \\text{ (if feasible)}, \\min_{i} \\left\\{ R_i \\mid R_i \\text{ from valid tangency solutions to } C_i \\right\\} \\right) $\n\nWhere for each $ i $, solve:\n$$\n(4 b_i^2 - 4 r_i^2) h^2 - 4 K_i b_i h + (K_i^2 - r_i^2 d^2) = 0\n$$\n\nFor each real root $ h $, compute $ R = \\sqrt{ (d/2)^2 + h^2 } $, and check if:\n- $ \\| M + h \\vec{n} - C_i \\| = R + r_i $, or\n- $ \\| M + h \\vec{n} - C_i \\| = R - r_i $ and $ R \\geq r_i $.\n\nThen take the minimum over all such valid $ R $.\n\n---\n\nThis is the formal mathematical problem statement.","simple_statement":null,"has_page_source":false}