310776: CF1886B. Fear of the Dark
Description
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 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.
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}$.
ExampleInput2 3 3 1 0 -1 6 3 3 -1 -1 4 3Output
3.6055512755 3.2015621187
Output
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,则你的答案将被接受。