#P18192. Getting Lost
Getting Lost
Getting Lost
题目描述
BaoBao 位于无限二维平面的点 ,他的家位于 。
平面上有 个圆形障碍,第 个障碍的圆心为 、半径为 。BaoBao 的移动路线不能经过任何障碍的内部,但可以接触障碍边界,也可以沿圆周移动。
当 BaoBao 到达某个点 ,同时满足下面两个条件时,就视为成功到家:
- ;
- 线段 不经过任何障碍的内部,允许与障碍相切。
求从 出发、成功到家所需的最短移动距离。只满足距离条件并不一定算到家,还必须满足到家的直线不被障碍挡住。
输入格式
第一行包含整数 ,表示测试组数。原题对测试组数的描述为约 组。
每组数据的第一行包含整数 。
第二行包含两个整数 。
第三行包含三个整数 。
接下来 行,第 行包含三个整数 。
输出格式
每组数据输出一行,表示最短移动距离。
设你的答案为 ,正确答案为 。当且仅当绝对误差或相对误差小于 时,答案被认为正确。
数据范围
- ;
- ;
- ;
- ;
- 起点 、家 均在所有障碍的外部或边界上;
- 任意两个障碍互不包含、互不相交,也不相切;
- 所有输入值均为整数。
移动路线和最终到达点可以位于整个无限平面上,不受输入坐标范围限制。
样例
输入:
2
1
10 0
0 0 2
6 0 1
0
0 10
0 0 5
输出:
8.209191463668802
5.000000000000000
样例解释
下图是第一组数据的原题示意图,绿色圆表示到家的距离范围,灰色圆为障碍,红色路线为最短路线。

路线由线段 、圆弧 和线段 组成,长度分别约为 、、,总长度约为 。