P13851 [CERC 2023] Going to the Moon
题目描述
爱丽丝和鲍勃正在他们豪宅外的沙地里玩一个游戏。地上画了一个圆，代表月亮，他们各自选择一个位置站立（可以在月亮内部、边界上或外部）。游戏的目标是：其中一名玩家尽可能快地跑向另一名玩家，但在途中必须触碰到月亮。
给定月亮、爱丽丝和鲍勃的位置，求从一名玩家出发，途中至少触碰（或穿过）月亮的边界或内部，并最终到达另一名玩家位置的最短路径长度。
输入格式
第一行包含一个整数 $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$。
输出格式
对于每个测试用例，输出一个实数，表示从 $A$ 到 $B$ 的最短路径长度，并且该路径至少触碰到圆 $C$（半径 $r$）的内部或边界。
当输出结果与标准答案的相对或绝对误差不超过 $10^{-6}$ 时，视为正确。
说明/提示
### 注释
下图展示了第一个测试用例的最优解路径：
:::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 完成