← 返回题目列表

Codeforces · 1886/B

B. 对黑暗的恐惧

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

Monocarp 试图下班回家。他目前位于二维平面的 $$$O = (0, 0)$$$ 点;他的房子位于$$$P = (P_x, P_y)$$$ 点。

不幸的是,已经是晚上了,所以天很黑。 Monocarp 害怕黑暗。他想沿着一条有什么东西照亮的路回家。

值得庆幸的是,有两个灯笼,位于 $$$A = (A_x, A_y)$$$ 和 $$$B = (B_x, B_y)$$$ 点。您可以选择任何非负数 $$$w$$$ 并将两个灯笼的功率设置为 $$$w$$$。如果灯笼的功率设置为 $$$w$$$,它将照亮以灯笼位置为中心、半径为 $$$w$$$ 的圆(包括圆的边界)。

您必须为灯笼的功率选择最小非负值$$$w$$$,以便从点$$$O$$$到点$$$P$$$有一条完全被照亮的路径。您可能会认为灯笼不会干扰 Monocarp 的移动。

前两个测试用例的图片

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由三行组成:

- 第一行包含两个整数 $$$P_x$$$ 和 $$$P_y$$$ ($$$-10^3 \le P_x, P_y \le 10^3$$$) — Monocarp 房子的位置;
- 第二行包含两个整数 $$$A_x$$$ 和 $$$A_y$$$ ($$$-10^3 \le A_x, A_y \le 10^3$$$) — 第一个灯笼的位置;
- 第三行包含两个整数 $$$B_x$$$ 和 $$$B_y$$$ ($$$-10^3 \le B_x, B_y \le 10^3$$$) — 第二个灯笼的位置。

输入的附加约束:

- 在每个测试用例中,点 $$$O$$$、$$$P$$$、$$$A$$$ 和 $$$B$$$ 彼此不同。

输出

对于每个测试用例,将答案打印在单独的行上 - 一个实数等于 $$$w$$$ 的最小值,这样从点 $$$O$$$ 到点 $$$P$$$ 有一条完全照亮的路径。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则您的答案将被视为正确 — 正式来说,如果您的答案是 $$$a$$$,而陪审团的答案是 $$$b$$$,则如果 $$$\dfrac{|a - b|}{\max(1, b)} \le 10^{-6}$$$,您的答案将被接受。

示例

输入 #1

2
3 3
1 0
-1 6
3 3
-1 -1
4 3

输出 #1

3.6055512755
3.2015621187