310776: CF1886B. Fear of the Dark

B. Fear of the Darktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Monocarp tries to get home from work. He is currently at the point $O = (0, 0)$ of a two-dimensional plane; his house is at the point $P = (P_x, P_y)$.

Unfortunately, it is late in the evening, so it is very dark. Monocarp is afraid of the darkness. He would like to go home along a path illuminated by something.

Thankfully, there are two lanterns, located in the points $A = (A_x, A_y)$ and $B = (B_x, B_y)$. You can choose any non-negative number $w$ and set the power of both lanterns to $w$. If a lantern's power is set to $w$, it illuminates a circle of radius $w$ centered at the lantern location (including the borders of the circle).

You have to choose the minimum non-negative value $w$ for the power of the lanterns in such a way that there is a path from the point $O$ to the point $P$ which is completely illuminated. You may assume that the lanterns don't interfere with Monocarp's movement.

The picture for the first two test cases Input

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains two integers $P_x$ and $P_y$ ($-10^3 \le P_x, P_y \le 10^3$) — the location of Monocarp's house;
• the second line contains two integers $A_x$ and $A_y$ ($-10^3 \le A_x, A_y \le 10^3$) — the location of the first lantern;
• the third line contains two integers $B_x$ and $B_y$ ($-10^3 \le B_x, B_y \le 10^3$) — the location of the second lantern.

Additional constraint on the input:

• in each test case, the points $O$, $P$, $A$ and $B$ are different from each other.

Output

For each test case, print the answer on a separate line — one real number equal to the minimum value of $w$ such that there is a completely illuminated path from the point $O$ to the point $P$.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$ — formally, if your answer is $a$, and the jury's answer is $b$, your answer will be accepted if $\dfrac{|a - b|}{\max(1, b)} \le 10^{-6}$.

ExampleInput

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

Output

3.6055512755
3.2015621187

题目大意：
Monocarp晚上回家，需要从原点O(0,0)走到家P(Px,Py)，但由于天黑他害怕，所以他希望走的路径能被两盏灯笼照亮。这两盏灯笼分别位于A(Ax,Ay)和B(Bx,By)点，你可以为两盏灯笼设定相同的非负功率w，功率为w的灯笼能照亮以灯笼位置为中心，半径为w的圆形区域（包括圆周）。你的任务是找到最小的非负值w，使得存在一条从O点到P点完全被照亮的路径。你可以假设灯笼不会影响Monocarp的移动。

输入输出数据格式：
输入：
- 第一行是一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行是两个整数Px和Py（-10^3≤Px,Py≤10^3），表示Monocarp家的位置。
- 第二行是两个整数Ax和Ay（-10^3≤Ax,Ay≤10^3），表示第一盏灯笼的位置。
- 第三行是两个整数Bx和By（-10^3≤Bx,By≤10^3），表示第二盏灯笼的位置。
- 输入附加条件：在每一个测试用例中，点O、P、A和B两两不同。

输出：
- 对于每个测试用例，输出一行，包含一个实数，表示最小的w值，使得存在一条完全被照亮的路径从O点到P点。
- 你的答案将被认为是正确的，如果其绝对或相对误差不超过10^-6。形式上，如果你的答案是a，而裁判答案是b，如果你的答案满足|a - b| / max(1, b) ≤ 10^-6，则你的答案将被接受。题目大意： Monocarp晚上回家，需要从原点O(0,0)走到家P(Px,Py)，但由于天黑他害怕，所以他希望走的路径能被两盏灯笼照亮。这两盏灯笼分别位于A(Ax,Ay)和B(Bx,By)点，你可以为两盏灯笼设定相同的非负功率w，功率为w的灯笼能照亮以灯笼位置为中心，半径为w的圆形区域（包括圆周）。你的任务是找到最小的非负值w，使得存在一条从O点到P点完全被照亮的路径。你可以假设灯笼不会影响Monocarp的移动。 输入输出数据格式： 输入： - 第一行是一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行是两个整数Px和Py（-10^3≤Px,Py≤10^3），表示Monocarp家的位置。 - 第二行是两个整数Ax和Ay（-10^3≤Ax,Ay≤10^3），表示第一盏灯笼的位置。 - 第三行是两个整数Bx和By（-10^3≤Bx,By≤10^3），表示第二盏灯笼的位置。 - 输入附加条件：在每一个测试用例中，点O、P、A和B两两不同。 输出： - 对于每个测试用例，输出一行，包含一个实数，表示最小的w值，使得存在一条完全被照亮的路径从O点到P点。 - 你的答案将被认为是正确的，如果其绝对或相对误差不超过10^-6。形式上，如果你的答案是a，而裁判答案是b，如果你的答案满足|a - b| / max(1, b) ≤ 10^-6，则你的答案将被接受。