#P4739. 定向越野
定向越野
题目描述
牛牛参加定向越野,要在平地上从起点 到达终点 。地图上有一些圆形水域,它们的内部互不相交。牛牛不能经过水域的内部,但可以沿圆的边界前进。若两片水域相切,牛牛可以经过它们的切点。
求符合条件的最短路线长度。
输入格式
第一行包含四个实数 ,表示起点和终点的坐标。
第二行包含整数 ,表示水域数。接下来 行,每行包含三个整数 ,表示一个圆形水域的圆心 和半径 。
输出格式
输出一行一个实数,将最短路线长度四舍五入至小数点后恰好一位。评测按这一位小数的结果比较。测试保证四舍五入后的结果与准确值的绝对误差不超过 。
样例 #1
样例输入 #1
2 1 20 11
2
5 5 4
16 9 4
样例输出 #1
23.0
数据范围
,所有坐标均在 内,。保证起点与终点不重合,且都在全部水域之外。