D. The three-fountain problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After so many years of competition your friend Marcos has decided to quit competitive programming, he is tired of solving problems. In this radical change of life he has decided to open a little newsstand in the park where he can enjoy a quieter life.

The problem is that the park where he wants to work has 3 fountains that are active all afternoons. Marcos doesn't want his customers to become wet while chatting with them as they choose their newspaper, so he's looking for the perfect place to set up his store.

The amount of water that reaches each point of the park is defined by the fountain closest to it. It is true that the rest of the fountains also wet, but it is so little that it can be ignored. Therefore, Mark's objective is to place his tent in such a way as to maximize the distance to the nearest fountain, i.e., to maximize the value of $$$\texttt{DRYNESS}$$$ described by: $$$$$$\texttt{DRYNESS}(p) =\min \{ d(p,F_1), d(p,F_2), d(p,F_3) \}$$$$$$ where $$$F_1$$$,$$$F_2$$$ y $$$F_3$$$ represent the positions of the fountains and the function $$$d(p, q)$$$ represents the Euclidean distance in the plane between two points $$$p$$$ and $$$q$$$, that is, the usual distance in a straight line.

Knowing that the park enclosure is a perfect square of side $$$100$$$ and its lower left corner is at the point $$$(0,0)$$$, can you indicate what is the largest value of $$$\texttt{DRYNESS}$$$ that Marcos will be able to achieve by placing his new store?

Input

The input starts with a number $$$N$$$, the number of test cases to be processed. Each test case is composed of 3 lines, each indicating a pair of numbers $$$(F_x,F_y)$$$, the position of one of the fountains. All these values will be indicated with 3 decimal places, using the point as decimal separator.

  • $$$ 1 \le N \le 10^4$$$
  • $$$0 \le F_{1x},F_{2x},F_{3x},F_{1y},F_{2y},F_{3y} \le 100$$$
  • $$$(F_{1x},F_{1y}) \neq (F_{2x},F_{2y})$$$
  • $$$(F_{1x},F_{1y}) \neq (F_{3x},F_{3y})$$$
  • $$$(F_{2x},F_{2y}) \neq (F_{3x},F_{3y})$$$
Output

The output for each case will indicate a three digits rounded number (using the point as decimal separator), the maximum value of DRYNESS that Marcos can achieve by placing his tent in the park.

Example
Input
1
19.000 13.000
10.000 81.000
73.000 44.000
Output
62.169
Note

To print a number $$$x$$$ with 3 decimal digits, you can use:

  • C++ 

        std::cout « std::fixed « std::setprecision(3) « x « std::endl;
  • Java 

        double round = Math.round(x * 1000.0) / 1000.0;
        String numberRounded = String.format("    System.out.println(numberRounded);
  • Python 

        print(f'{x:.3f}')