P6671 [Tsinghua Training 2016] Orienteering

Orienteering is a sport that combines both intelligence and physical strength. In this activity, contestants need to start from the starting point and reach the specified destination in the shortest possible time. Niuniu likes this sport very much, but he does not know how to reach the finish faster. He heard that you, who came to the training camp, are very smart, so he handed you the orienteering map and hopes you can help him solve some problems. The map Niuniu gives you describes a flat ground. The map not only clearly marks the coordinates of the start and the end, but also marks several pairwise disjoint circular regions, each representing a circular water area. For Niuniu who cannot swim, entering water is impossible at all. Therefore, Niuniu's route cannot pass through any water area. Niuniu wants to know what the minimum possible length of such a route is.

The first line contains four real numbers $S_x,S_y,T_x,T_y$, representing the coordinates of the starting point and the ending point. The second line contains an integer $n$, representing the number of water areas. The next $n$ lines each contain $3$ integers $x_i,y_i,r_i$, representing the coordinates of the center and the radius of a water area. It is guaranteed that both the start and the end are not inside or on the boundary of any water area, and the start and the end do not coincide.

Output one line containing one real number, rounded to exactly $1$ digit after the decimal point, representing the answer. Your output must be exactly the same as the standard output to be considered correct. The testdata guarantees that the absolute difference between the rounded answer and the exact answer is at most $4×10^{−2}$. (If you do not know what floating-point error is, you can understand this as: for most algorithms, you can use floating-point types normally without any special handling.)

#### Sample Explanation The map is shown in the figure below, and the drawn path is the required shortest path.  #### Constraints All data satisfy $0≤n≤500$, $−1000≤x_i,y_i,r_i,S_x,S_y,T_x,T_y≤1000$。 Translated by ChatGPT 5