Training Site
Sideways banner


Input: Standard Input (stdin)
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.


The first line contains 4 space-separated 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 a single floating-point number, the minimum distance Roxy must travel in the sun. You must output the distance within a 10^{-4} error.


  • -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


  • Subtask 1 (+20%): N=1
  • Subtask 2 (+30%): N \leq 20
  • Subtask 3 (+50%): No further constraints.


For students using C++, std::cout by default does not print floating-point 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
    2.0 0.0 1.0

    Sample Output 1

  • Sample Input 2

    0.0 1.0 20.0 -6.0
    -1.0 -2.0 1.0
    4.0 2.0 3.0
    7.0 -6.0 2.0

    Sample Output 2