Enshadowed
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds
It's yet another sweltering day at the University of Canterbury. Roxy needs to get between her lectures, and wants to stay out of the sun as much as possible.
Luckily, there are some trees on campus providing delicious shade. The university keeps their grounds meticulously maintained, and the treetops are topiaried into perfect spheres. The shadows of the trees are thus all circular in shape. (The trunks of the trees also happen to be infinitesimally thin, thus casting no shadow). The campus grounds are famously flat, so assume all distances are on a flat 2D plane.
Given Roxy's position and destination, and the centers and radii of the shadows, output the minimum distance Roxy must travel in the sun to get to her lecture.
Input
The first line contains 4 spaceseparated numbers, x_R y_R x_L y_L, where (x_R, y_R) are Roxy's (Cartesian) coordinates and (x_L, y_L) are the coordinates of her destination. The second line contains a single integer N, the number of shadows. The following N lines each contain three space separated numbers, x_C y_C r, indicating there is a shadow centered at (x_C, y_C) with radius r.
Output
Output a single floatingpoint number, the minimum distance Roxy must travel in the sun. You must output the distance within a 10^{4} error.
Constraints
 1000 \leq x_R, y_R, x_L, y_L, x_C, y_C \leq 1000
 0 \leq r \leq 1000
 1 \leq N \leq 500
Subtasks
 Subtask 1 (+20%): N=1
 Subtask 2 (+30%): N \leq 20
 Subtask 3 (+50%): No further constraints.
Note
For students using C++, std::cout
by default does not print floatingpoint numbers with enough precision to pass the test data. Instead use printf
or set the precision manually with std::cout.precision()
.

Sample Input 1
0.0 0.0 4.0 0.0 1 2.0 0.0 1.0
Sample Output 1
2.000000

Sample Input 2
0.0 1.0 20.0 6.0 3 1.0 2.0 1.0 4.0 2.0 3.0 7.0 6.0 2.0
Sample Output 2
15.667109