题目描述

Alice and Bob are playing a game in the sand outside their mansion. A circle representing the Moon is drawn somewhere, and they each also pick a place to stand (inside, on the edge, or outside the Moon). The goal of the game is that one of the players runs to the other as fast as possible, while also touching the Moon during the run.

Given the positions of the Moon, Alice, and Bob, find the length of the shortest path that starts at one of the players, touches (or crosses) the edge or the interior of the Moon, and ends at the position of the other player.

输入格式

The first line contains an integer $T$, the number of test cases. It’s followed by $T$ lines, each containing 7 space-separated integers $x_A$, $y_A$, $x_B$, $y_B$, $x_C$, $y_C$, $r$, representing coordinates of Alice, $A = (x_A, y_A)$, Bob, $B = (x_B, y_B)$, the center of the circle, $C = (x_C, y_C)$, and its radius $r$.

输出格式

For each test case output a single decimal number representing the length of the shortest path from $A$ to $B$ that also touches at least one point inside or on the edge of a circle with the center $C$ and radius $r$. The solution will be considered correct if the relative or absolute error compared to the official solution is within $10^{-6}$.

2
0 0 2 0 -1 2 1
5 0 3 0 2 0 2

3.9451754612261913
2

提示

Comment

The solution for the first test case is shown in the picture.

:::align{center} :::align

Input limits

• $1 \leq T \leq 10^3$
• $-10^3 \leq x_A, y_A, x_B, y_B, x_C, y_C \leq 10^3$
• $0 \leq r \leq 10^3$