33746번 - Five Steiner 스페셜 저지다국어

문제

After reading the paper Steiner minimal trees on sets of four points, one has decided to make things a bit harder. Why not five points instead?

You are given 5ドル$ points with integer coordinates on the plane. The distance between two points is defined by the Euclidean distance.

Please find the sum of distances of the minimum weight$^\dagger$ steiner tree$^\ddagger$ of the given points.

$^\dagger$ The weight of a tree is defined by the sum of distances between all pairs of points connected by edges.

$^\ddagger$ A steiner tree is defined as a tree spanning the given points, possibly containing some arbitrary number of points added to the point set. The added points need not have integer coordinates.

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ (1ドル \le t \le 10$). The description of the test cases follows.

Each test case consists of five lines, containing the following input.

1. Two integers $x_a$ and $y_a,ドル the coordinates of the first point $A$. ($-10^5 \le x_a,y_a \le 10^5$)
2. Two integers $x_b$ and $y_b,ドル the coordinates of the second point $B$. ($-10^5 \le x_b,y_b \le 10^5$)
3. Two integers $x_c$ and $y_c,ドル the coordinates of the third point $C$. ($-10^5 \le x_c,y_c \le 10^5$)
4. Two integers $x_d$ and $y_d,ドル the coordinates of the fourth point $D$. ($-10^5 \le x_d,y_d \le 10^5$)
5. Two integers $x_e$ and $y_e,ドル the coordinates of the fifth point $E$. ($-10^5 \le x_e,y_e \le 10^5$)

출력

For each test case, print the sum of distances of the minimum steiner tree of the given points on one line.

Your output will be accepted if the absolute or relative error does not exceed 10ドル^{-5}$.

제한

힌트