#P18192. Getting Lost

Getting Lost

Getting Lost

题目描述

BaoBao 位于无限二维平面的点 A=(ax,ay)A=(a_x,a_y),他的家位于 B=(bx,by)B=(b_x,b_y)。

平面上有 nn 个圆形障碍,第 ii 个障碍的圆心为 (xi,yi)(x_i,y_i)、半径为 rir_i。BaoBao 的移动路线不能经过任何障碍的内部,但可以接触障碍边界,也可以沿圆周移动。

当 BaoBao 到达某个点 PP,同时满足下面两个条件时,就视为成功到家:

  1. ∣PB∣≤R|PB|\le R;
  2. 线段 PBPB 不经过任何障碍的内部,允许与障碍相切。

求从 AA 出发、成功到家所需的最短移动距离。只满足距离条件并不一定算到家,还必须满足到家的直线不被障碍挡住。

输入格式

第一行包含整数 TT,表示测试组数。原题对测试组数的描述为约 6060 组。

每组数据的第一行包含整数 nn。

第二行包含两个整数 ax,aya_x,a_y。

第三行包含三个整数 bx,by,Rb_x,b_y,R。

接下来 nn 行,第 ii 行包含三个整数 xi,yi,rix_i,y_i,r_i。

输出格式

每组数据输出一行,表示最短移动距离。

设你的答案为 uu,正确答案为 vv。当且仅当绝对误差或相对误差小于 10−610^{-6} 时,答案被认为正确。

数据范围

  • 0≤n≤20\le n\le2;
  • −104≤ax,ay,bx,by,xi,yi≤104-10^4\le a_x,a_y,b_x,b_y,x_i,y_i\le10^4;
  • 0≤R≤1040\le R\le10^4;
  • 0<ri≤1040<r_i\le10^4;
  • 起点 AA、家 BB 均在所有障碍的外部或边界上;
  • 任意两个障碍互不包含、互不相交,也不相切;
  • 所有输入值均为整数。

移动路线和最终到达点可以位于整个无限平面上,不受输入坐标范围限制。

样例

输入:

2
1
10 0
0 0 2
6 0 1
0
0 10
0 0 5

输出:

8.209191463668802
5.000000000000000

样例解释

下图是第一组数据的原题示意图,绿色圆表示到家的距离范围,灰色圆为障碍,红色路线为最短路线。

第一组样例的切线、障碍圆弧与最终到达点

路线由线段 ADAD、圆弧 DE^\widehat{DE} 和线段 EFEF 组成,长度分别约为 3.87298334623.8729833462、0.42012833440.4201283344、3.91607978313.9160797831,总长度约为 8.20919146378.2091914637。