10224-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. Luke's position is specified by a pair of coordinates ( xluke , yluke ) within the plane. The Ewok village has coordinates ( xewok , yewok ). You are to find the shortest travel time from Luke's position to the Ewok village.

The first line of input contains the number of test cases followed by a blank line. The first line of each test case contain T, xluke , yluke xewok , yewok . T lines follow; each gives the coordinates and diameter of a tree: xtreei , ytreei , dtreei . T is an integer not exceeding 10; coordinates and diameters are real numbers in miles. Trees do not intersect or touch one another. There is a blank line between each consecutive test case.

For each test case output is a single real number, to two decimal places, giving the minimum travel time in seconds. Print a blank line
between 2 consecutive data sets.
[[/==]]

Sample Input:

1

2 0.0 0.0 10.0 0.0
4.0 0.0 1.0
6.0 0.0 1.0

Output:


181.13

Link to UVA site

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License