Problem F
Return of the Jedi

Luke Skywalker races through the forest on a speeder bike, trying to outrun a patrol of Imperial scouts on Endor. A small moon near a new Death Star, Endor is covered by dense foliage and a thick forest of ancient towering trees. The speeder bike, which Luke stole from an Imperial scout, is an antigravity vehicle capable of speeds of $200$ miles an hour. How quickly can Luke reach Princess Leia in the Ewok village?

The forest is a plane with $T$ trees. Each tree trunk is a circle. Luke’s position is specified by a pair of coordinates $(x_{luke}, y_{luke})$ within the plane. The Ewok village has coordinates $(x_{ewok}, y_{ewok})$. You are to find the shortest travel time from Luke’s position to the Ewok village.


The first line of input contains five numbers $T$, $x_{\mathrm{luke}}$, $y_{\mathrm{luke}}$, $x_{\mathrm{ewok}}$,$y_{\mathrm{ewok}}$. $T$ is a non-negative integer not exceeding $10$, the number of trees. Then follow $T$ lines, each giving the coordinates and diameter of a tree: $x_{\mathrm{tree}_{i}}$, $y_{\mathrm{tree}_{i}}$, $d_{\mathrm{tree}_{i}}$. Coordinates and diameters are real numbers in miles with at most one digit after the decimal point. Each coordinate is between $-100$ and $100$ (inclusive), and each diameter is between $0.1$ and $200$ (inclusive).

Trees do not intersect or touch one another. Luke’s position and the position of the Ewok village do not touch or lie inside any tree.


Output is a single real number, giving the minimum travel time in seconds. The output should be accurate to within an absolute or relative error of at most $10^{-6}$.

Sample Input 1 Sample Output 1
2 0.0 0.0 10.0 0.0
4.0 0.0 1.0
6.0 0.0 1.0
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Source Waterloo Programming Contest 2002-01-26
License For educational use only

Please log in to submit a solution to this problem

Log in