Shortest Orienteering Path

This problem is based on an orienteering sport where competitors must travel from a starting point to a finishing point in the minimum possible distance. However, the path cannot cross any circular water zones because the competitor cannot swim. The map is a flat plane with the start and finish coordinates clearly marked, and several non-intersecting circles denote the water areas. A path is valid if it does not enter the interior of any water circle (touching the boundary is allowed).

Mathematically, if you have two points \( A=(x_A,y_A) \) and \( B=(x_B,y_B) \), the Euclidean distance is given by \[ d(A,B)=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2}, \] while the length of an arc on a circle of radius \( r \) over an angle \( \theta \) (in radians) is \[ L = r\theta. \]

Your task is to compute the minimum route length from the start to the finish that avoids going through any water area. The input describes the start and finish coordinates, followed by the number of water areas and each water area’s center coordinates and radius.

Note: It is guaranteed that the water areas (circles) do not intersect. Your answer will be accepted if its absolute or relative error does not exceed 10^-6.

inputFormat

The input is given as follows:

 x_start y_start x_end y_end
 n
 cx1 cy1 r1
 cx2 cy2 r2
 ...
 cxn cyn rn

Here, (x_start, y_start) and (x_end, y_end) are the coordinates of the start and finish respectively. n is the number of water areas. Each water area is given by its center (cx, cy) and its radius r. All numbers are floating‐point numbers.

outputFormat

Output the minimum route length as a floating-point number. If the route from start to finish is already clear (i.e. does not cross any water area), then output the Euclidean distance between start and finish.

sample

0 0 10 0
0

10.000000