{"raw_statement":[{"iden":"statement","content":"伊森是一个传奇的间谍人物，他所带领的 \"不可能任务小组\" 总能拯救世界于危难之中。\n\n这次，伊森在这栋大楼里执行一项绝密的情报任务，但是面前这条幽长的走廊通道却拦住了他，走廊间安装了许多警报传感器。每个传感器都有自己的感知范围。如果人身体的某个部位在传感器感知的范围内，那么将会触动整栋大楼的中央报警装置，敌方也将会很快察觉并采取相应的措施。\n\n为了能够在不触动报警装置的情况下悄悄通过这条走廊，伊森也许需要一些特殊的紧身装备来控制他的身材。同步协助伊森行动的小组成员班吉在收到伊森求助后，立即通过技术手段将整条走廊建模在二维平面上。如下图，整个走廊可以视为二维平面上由 $y = 0$ 与 $y = w$ 两条直线所框定的白色区域，中间有若干的报警传感器位于墙壁上或者走廊中。伊森在模型中可以视为具有一定半径的圆，位于走廊的最左侧 $x = -infinity$，想穿过走廊到达最右侧 $x = + infinity$。班吉需要尽快计算出该圆可以具有的最大半径，以便可以悄悄通过这条走廊而不触发报警装置，聪明的你快帮帮他！\n\n第一行输入一个正整数 $T \" \"(1 <= T <= 100)$，表示数据组数。接下来 $T$ 组数据，每组数据均满足：\n\n对于每组数据，请输出一个浮点数，表示能够顺利通过这条走廊而不触发报警装置的人的最大半径，注意换行。输出结果要求精确到 $10^(-6)$，若精确答案为 $a$，你的输出结果为 $b$，只要满足 $| a -b | < 10^(-6)$，评测法官 Jury 就认为你的输出是正确的。\n\n"},{"iden":"input","content":"第一行输入一个正整数 $T \" \"(1 <= T <= 100)$，表示数据组数。接下来 $T$ 组数据，每组数据均满足：  第一行输入一个正整数 $w \" \"(1 <= w <= 10^5)$，表示这条走廊的宽度，建模后墙壁的边缘分别为直线 $y = 0$ 与 $y = w$。 第二行输入一个非负整数 $n \" \"(0 <= n <= 10^3)$，表示报警传感器的数目，编号从 $1$ 到 $n$。 接下来 $n$ 行，第 $i$ 行输入三个整数 $x_i, y_i$ 和 $r_i \" \"(-10^5 <= x_i <= 10^5, \" \"0 <= y_i <= w, \" \"1 <= r_i <= 10^5)$ 并由空格间隔开，表示传感器建模后的坐标与感知范围。"},{"iden":"output","content":"对于每组数据，请输出一个浮点数，表示能够顺利通过这条走廊而不触发报警装置的人的最大半径，注意换行。输出结果要求精确到 $10^(-6)$，若精确答案为 $a$，你的输出结果为 $b$，只要满足 $| a -b | < 10^(-6)$，评测法官 Jury 就认为你的输出是正确的。"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case:  \n- Let $ w \\in \\mathbb{R}^+ $ be the vertical width of the corridor, bounded by lines $ y = 0 $ and $ y = w $.  \n- Let $ n \\in \\mathbb{Z}^+ $ be the number of sensors.  \n- Let $ S = \\{ (x_i, y_i, r_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of sensors, where each sensor is a disk centered at $ (x_i, y_i) $ with radius $ r_i $, representing its detection range.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each test case:  \n   - $ 1 \\le n \\le 1000 $  \n   - $ 1 \\le w \\le 10^9 $  \n   - $ x_i, y_i, r_i \\in \\mathbb{R} $, with $ 0 \\le y_i \\le w $, $ r_i \\ge 0 $  \n\n**Objective**  \nFind the maximum radius $ R \\in \\mathbb{R}^+ $ such that a disk of radius $ R $, starting from $ x = -\\infty $ and moving to $ x = +\\infty $, can traverse the corridor without intersecting any sensor disk or the boundaries $ y = 0 $, $ y = w $.  \n\nThis is equivalent to finding the largest $ R $ for which there exists a continuous path from $ x = -\\infty $ to $ x = +\\infty $ within the strip $ R \\le y \\le w - R $, avoiding all disks $ (x_i, y_i, r_i + R) $.  \n\n**Formal Reduction**  \nDefine the forbidden region for the center of the moving disk as the union of:  \n- The expanded sensor disks: $ \\bigcup_{i=1}^n \\mathcal{D}((x_i, y_i), r_i + R) $  \n- The boundary bands: $ \\{ (x,y) \\mid y < R \\} \\cup \\{ (x,y) \\mid y > w - R \\} $  \n\nThe maximum $ R $ is the largest value such that the corridor region $ \\mathbb{R} \\times [R, w - R] $ is not fully blocked by the union of expanded sensor disks.  \n\nThis reduces to a **circle-packing connectivity problem**: compute the maximum $ R $ such that the expanded sensor disks do not disconnect the left and right boundaries of the strip $ [R, w - R] $.  \n\n**Solution Approach**  \nUse binary search on $ R \\in [0, w/2] $. For each candidate $ R $, construct a graph where nodes are sensors and the two boundaries ($ y = 0 $, $ y = w $). Connect two nodes if their expanded disks (radius $ r_i + R $) intersect. Also connect a sensor to a boundary if its expanded disk intersects the boundary.  \n\nIf the top boundary ($ y = w $) and bottom boundary ($ y = 0 $) are connected via this graph, then the path is blocked.  \n\nThe maximum allowable $ R $ is the largest value for which the top and bottom boundaries are **not** connected.","simple_statement":"Find the maximum radius of a circle that can pass from left to right through a corridor between y=0 and y=w without touching any sensors.","has_page_source":false}