#P4739. 定向越野

    ID: 3859 传统题 4500ms 512MiB 尝试: 61 已通过: 10 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何切线可见图点到线段距离平方距离比较图论DijkstraCF2500

定向越野

题目描述

牛牛参加定向越野,要在平地上从起点 SS 到达终点 TT。地图上有一些圆形水域,它们的内部互不相交。牛牛不能经过水域的内部,但可以沿圆的边界前进。若两片水域相切,牛牛可以经过它们的切点。

求符合条件的最短路线长度。

输入格式

第一行包含四个实数 Sx,Sy,Tx,TyS_x,S_y,T_x,T_y,表示起点和终点的坐标。

第二行包含整数 nn,表示水域数。接下来 nn 行,每行包含三个整数 xi,yi,rix_i,y_i,r_i,表示一个圆形水域的圆心 (xi,yi)(x_i,y_i) 和半径 rir_i。

输出格式

输出一行一个实数,将最短路线长度四舍五入至小数点后恰好一位。评测按这一位小数的结果比较。测试保证四舍五入后的结果与准确值的绝对误差不超过 4×10−24\times10^{-2}。

样例 #1

样例输入 #1

2 1 20 11
2
5 5 4
16 9 4

样例输出 #1

23.0

数据范围

0≤n≤5000\le n\le500,所有坐标均在 [−1000,1000][-1000,1000] 内,0≤ri≤10000\le r_i\le1000。保证起点与终点不重合,且都在全部水域之外。