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)