P16626 [GKS 2017 #D] Trash

Bob 是一位出色的 Google 员工。他追求效率，因此每件事都做得又快又好。今天，Bob 发现自己办公桌旁的垃圾桶不见了！不幸的是，这意味着他必须改用附近另一个垃圾桶。由于离开座位去丢垃圾会降低他的工作效率，Bob 决定将垃圾直接扔进那个垃圾桶！ 但是 Google 办公室中有很多障碍物。例如，如果扔出的垃圾砸到人、墙壁或其他任何东西，都是不礼貌的行为。Bob 希望扔出的垃圾不碰到任何现有的障碍物。 为简化问题，我们只考虑包含 Bob 和垃圾桶的竖直平面。Bob 位于点 $(0, 0)$，垃圾桶位于点 $(P, 0)$。此外，办公室中有 $N$ 个障碍物，每个障碍物是一个点，第 $i$ 个障碍物的坐标为 $(X_i, Y_i)$。办公室的天花板是一条直线，在平面中的表达式为 $y = H$。由于 Bob 在一座新型高科技悬浮办公室中，本题不考虑办公室的地面，你无需担心与地面的碰撞。Bob 会扔出一块半径为 $R$ 的圆形垃圾。垃圾的圆心从 $(0, 0)$ 出发。当垃圾被抛出时，其圆心必须沿着一条抛物线轨迹运动，表达式为 $f(x) = a x (x - P)$，其中 $0 \le x \le P$，且 $a$ 可以是任意小于等于 $0$ 的实数。只有当垃圾的圆心到达垃圾桶所在点时，才认为垃圾已抛出，仅垃圾的一部分触碰到该点是不够的。 Bob 想知道：在不碰到天花板和任何障碍物的前提下，他能扔出的最大垃圾半径是多少？即，我们需要找到最大的 $R$，使得存在至少一个 $a$ 满足以下条件：对于任意 $0 \le x \le P$，点 $(x, f(x))$ 与 $(x, H)$ 之间的欧几里得距离大于 $R$；并且对于每个 $i$，点 $(x, f(x))$ 与 $(X_i, Y_i)$ 之间的欧几里得距离大于等于 $R$。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$P$ 和 $H$：障碍物的数量、垃圾桶的 $x$ 坐标以及天花板的高度。随后有 $N$ 行，其中第 $i$ 行表示第 $i$ 个障碍物，包含两个整数 $X_i$ 和 $Y_i$，表示该障碍物的坐标。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个浮点数，表示最大半径 $R$。如果答案与正确答案的绝对误差或相对误差在 $10^{-4}$ 以内，则认为正确。

请注意，最后一个样例不会出现在小数据集中。 下图展示了样例 #1 的情况。Bob 位于 $(0, 0)$，垃圾桶位于 $(10, 0)$。有一个障碍物位于点 $(5, 3)$，用星号标记。如果 Bob 从障碍物上方扔垃圾，最大 $R$ 约为 $3.2387$，此时 $a$ 约为 $-0.2705$。如果 Bob 从障碍物下方扔垃圾，最大 $R$ 为 $3$，此时 $a = 0$。因此该样例的最大 $R$ 约为 $3.2387$。 :::align{center}  ::: 样例 #2 与样例 #1 类似，但障碍物升高了 1 个单位。此时，如果 Bob 从障碍物下方扔垃圾，最大 $R$ 为 $4$（对应 $a = 0$）。如果他从障碍物上方扔垃圾，最大 $R$ 仅约为 $2.8306$（对应 $a = -0.4$）。因此该样例的最大 $R$ 为 $4$。 ### 限制条件 $1 \le T \le 50$。 $2 \le P \le 1000$。 $2 \le H \le 1000$。 $0 < X_i < P$。 $0 < Y_i < H$。 **小数据集（测试集 1 – 可见）** $N = 1$。 **大数据集（测试集 2 – 隐藏）** $1 \le N \le 10$。 翻译由 DeepSeek V4 Pro 完成