Description

爱丽丝和鲍勃正在他们豪宅外的沙地里玩一个游戏。地上画了一个圆，代表月亮，他们各自选择一个位置站立（可以在月亮内部、边界上或外部）。游戏的目标是：其中一名玩家尽可能快地跑向另一名玩家，但在途中必须触碰到月亮。

给定月亮、爱丽丝和鲍勃的位置，求从一名玩家出发，途中至少触碰（或穿过）月亮的边界或内部，并最终到达另一名玩家位置的最短路径长度。

Input Format

第一行包含一个整数 $T$，表示测试用例的数量。
接下来 $T$ 行中，每行包含 7 个用空格分隔的整数 $x_A, y_A, x_B, y_B, x_C, y_C, r$，分别表示爱丽丝的位置 $A = (x_A, y_A)$，鲍勃的位置 $B = (x_B, y_B)$，圆心 $C = (x_C, y_C)$ 以及半径 $r$。

Output Format

对于每个测试用例，输出一个实数，表示从 $A$ 到 $B$ 的最短路径长度，并且该路径至少触碰到圆 $C$（半径 $r$）的内部或边界。
当输出结果与标准答案的相对或绝对误差不超过 $10^{-6}$ 时，视为正确。

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

3.9451754612261913
2

Hint

注释

下图展示了第一个测试用例的最优解路径：

:::align{center} :::align

输入限制

• $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$

翻译由 ChatGPT-5 完成