Fear of the Dark
Contest: Educational Codeforces Round 156 (Rated for Div. 2)
Difficulty rating: 1200
Tags: binary search, geometry, math

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 format:
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 format:
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}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
3 3
1 0
-1 6
3 3
-1 -1
4 3

Example output:
3.6055512755
3.2015621187

Editorial:
There are only two major cases: both points $$$O$$$ and $$$P$$$ lie inside the same circle, or the point $$$O$$$ lies inside one of the circles and $$$P$$$ lies inside the other circle.
Let's denote the distance between the points $$$P$$$ and $$$Q$$$ as $$$d(P, Q)$$$.
Let's look at the first case, when the points $$$O$$$ and $$$P$$$ lie inside the circle centered at $$$A$$$. In that case, inequalities $$$d(O, A) \le R$$$ and $$$d(P, A) \le R$$$ must be satisfied. Therefore, the minimum possible radius for that case is equal to $$$\max(d(O, A), d(P, A))$$$. Similarly, for the circle centered at $$$B$$$, the minimum possible radius for that case is equal to $$$\max(d(O, B), d(P, B))$$$.
Let's look at the second case, when the point $$$O$$$ lies inside the circle centered at $$$A$$$ and the point $$$P$$$ lies inside the circle centered at $$$B$$$. In that case, inequalities $$$d(O, A) \le R$$$ and $$$d(P, B) \le R$$$ must be satisfied. But there is one extra constraint: the circles must intersect, because there is should an illuminated path from one circle to another. This adds one more inequality — $$$d(A, B) \le 2R$$$. Therefore, the minimum possible radius for that case is equal to $$$\max\left(d(O, A), d(P, B), \frac{d(A, B)}{2}\right)$$$. Similarly, when $$$O$$$ lies inside the circle centered at $$$B$$$ and $$$P$$$ lies inside the circle centered at $$$A$$$, the minimum possible radius for that case is equal to $$$\max\left(d(O, B), d(P, A), \frac{d(A, B)}{2}\right)$$$.
So the answer to the problem is the minimum among aforementioned cases.