[[==]]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

wow, compared to the last two, this problem is insane! I hate floating point….

/d / ___\

/ s|t

d = s * t

200 m/h

with trees to avoid, but otherwise as the crow fly's ?

I am not sure on how the units work out for this question. Can anyone explain this one in simple terms?

also fail at wikidot markup

well, there are a large number of factors to consider. I don't know if I should be discussing it before the contest is over, because I may give out some hints that others haven't thought of (or in reverse, someone might give me hints I haven't thought of).

I'm treating this as ACM training (I can't ask for simple terms on the day =P), so all I'll say for now, is all the numbers you need are in the question. But it's a nightmare to properly implement them (unless i'm overcomplicating it)

woo don't take it that seriously …. i already had posted 'test cases' when i found stupid problems in my code that meant it failed for the other 2. imho these are weekly things that don't even count for anything. Also, in the competition you work in teams.

I would rather put information here that gets some gets some one to finish it than sit on the information.

Feature: finish a task

As a mq acm competitor

I want to complete UVA example problems

So that I can be better prepared for the ACM

http://cukes.info/

well then here is what I did:

You have to get the shortest path between two points, that's easy, it's a straight line distance calculation. Then have to find any circles (trees) that lie on that line, again easy. Point-to-a-line formula will tell you how far the centre of a circle is to a line, if it's less than the radius of that circle, it intersects. For simple cases, find a line that goes from the start point, to the edge of the circle, then from the edge of the circle to the finish point. Recursively checking and adjusting for additional circles that cross any new lines. For more complex cases, you need to find the longest straight line that will attach to a circle, then from the apex of the circle to the finish. It takes in an arc of the total circumference of the circle (imagine if the start and end points lie on opposite sides of a circle, the shortest distance would be half the circumference).

Finally, calculate all these distances and use the formula dist/(200/3600) to get the final answer.

I used this to get *fairly* good results, but for the life of me I can't work out the precision. On the given input I get an answer of 181.1206395, which does not round to 181.13

yes. I was thinking you would have to do something like that - I really was only after the

dist/(200/3600) part btw ^^.

Try 2 DP - it might work for that. (um ceiling not floor perhaps ?)

Stephen, to print out as 2 decimal points, try something like printf("%.2f", time) or something like that - can't be sure of the syntax on top of my head

Sample data

7 0.0 0.0 100.0 0.0

2 0 2

4 -1 1.8

4 1 1.8

8 -1 4

8 4 5

50 -10 50

96 0 5

sample output

1895.44

sample data

7 0.0 0.0 0.0 100.0

0 2 2

-1 4 1.8

1 4 1.8

-1 8 4

4 8 5

-10 50 50

0 96 5

sample output

1895.44

Some big hints for this problem, since the deadline is past. I didn't actually implement this correctly, but the theory is sound. I apologise in advance if I'm giving away too much. But I worked so hard on the problem, I figured someone else may benefit if I post….

Here is the math behind what I did:

[http://i97.photobucket.com/albums/l237/stales2/acm/luke-ewok-1.png]

lx,ly is luke. ex,ey are the ewoks, cx,cy is a tree on their path.

d(lx,ly,cx,cy) is the distance from luke to the centre of the tree, calculated by distance formula.

r is the radius of the tree

ro can be calculated from the radius, the distance and pythagorus.

ro is the longest straight line from luke to the edge of the tree, and is the shortest path that he can follow to get around the tree (my drawing is not to scale and looks misleading)

[http://i97.photobucket.com/albums/l237/stales2/acm/luke-ewok-2.png]

Now with ro, we can draw a circle from luke's position, with radius ro. This circle will intersect the edge of the tree exactly twice. Each of these points needs to be calculated. (in my first diagram, the path below is shorter than the path above)

To find the exact locations of these points is done by a bit of algebra, I've got the working there (although the diagram is dodgy)

[http://i97.photobucket.com/albums/l237/stales2/acm/luke-ewok-3.png]

Now, what this gives you is the shortest path from luke to the edge of the circle, and from the edge of the circle to the finish. All that's left is to compute the distance around the circle. Finding the circumference of a circle is easy, 2piR. Finding an arc of that circle is fraction of this. The exact fraction can be calculated over the angle between these two points (for example, 1/2*2*pi*r = 180/360*pi*r). To find the angle, consider the two points as an isosceles triangle, with two sides length r (radius), the base of this tirangle is the distance between the two points . The isosceles triangle can be broken into two right-angle triangles. From that, trig gives the angle.

From that you have all the info to find the shortest route from start to finish.

But!

That's not all the work. This is the simple case of 1 triangle. You need to take care with more. I did this recursively, dividing the problem with every circle that intersected, find the new shortest path to the finish and the end. But I had some precision errors.

The last thing is calculating if a circle intersects a line. Two ways this can be done:

-point-to-line distance formula

-find the height of the triangle made by lx,ly:ex,ey:cx,cy. compare the height to the radius (I did it this way)

you are doing it wrong! use the force!