TopCoder problem "ShortCut" used in SRM 215 (Division I Level Three)



Problem Statement

    My 4WD SUV can drive anywhere. Around here I can drive cross-country at a constant speed that is exactly half of my road speed.

Given a section of one-way road that is a sequence of straight-line segments, I want to know the fastest way to get from the start of the section to the end of the section. I can leave and re-enter the road as often as I wish. Create a method suvTime that is given a int[] roadX and a int[] roadY and that finds the quickest route, returning the time required as a fraction of the time required if I had to stay on the road. So, for example, a return of .75 means that by using my SUV capabilities I can get to my destination in 3/4 of the time required if I had to follow the road.

The i-th elements of roadX and roadY give the coordinates of i-th point along the road, where the first elements gives the start point and the last elements give the end point.

 

Definition

    
Class:ShortCut
Method:suvTime
Parameters:int[], int[]
Returns:double
Method signature:double suvTime(int[] roadX, int[] roadY)
(be sure your method is public)
    
 

Constraints

-roadX will contain between 2 and 50 elements inclusive.
-roadY will contain the same number of elements as roadX.
-Each element in roadX and in roadY will be between -1000 and 1000 inclusive.
-No two road segments will touch or intersect (except that the last point of a segment is the first point of the next segment).
 

Examples

0)
    
{10,14,14}
{0,0,4}
Returns: 1.0
        E
        x
        x
        x
    Sxxxx
'S' is the start point, 'E' the end, and 'x' shows the road. Cross country might be fun, but leaving the road in this case would be a mistake. It could shorten the distance of the trip, but it would increase the time taken.
1)
    
{0,4,4}
{0,4,-4}
Returns: 0.8001991549907409
       x
      xx
     x x
    x  x
   S   x
    \  x
     \ x
       x
       E
The \ shows the appropriate shortcut, which is directly from the start point to a little south on the final segment. This off-road leg has length 4.6188 and rejoins the road at a point where the remaining on-road travel has length 1.7. The original road distance was about 13.66 (5.66 northeastward, 8 southward). The shortcut reduces the trip to an equivalent road distance of 2*4.6188 + 1.7 = 10.93 which requires only about 80% of the time required by those pitiful non-SUV owners.
2)
    
{0,100,100,-100,-100,100}
{0,0,20,20,40,40}
Returns: 0.2962962962962963
  
       xxxxxxxxxxxxxxxxxxxxE
       x            /
       xxxxxxxxxxxxxxxxxxxxx
                  /        x
                 Sxxxxxxxxxx
Here the best path is to go cross country to the final part of the road and follow it to the destination. The long middle part of the road is no help because it is one-way the wrong way.
3)
    
{0,-100,-100,100,90}
{0,0,20,20,40}
Returns: 0.4585856530883108
                      E
                    /  x
    xxxxxxxxxxxxxxxxxxxxx
    x          /
    xxxxxxxxxxS
The fastest way is to cut cross-country to the long middle straightline part of the road, follow it for a while, and then cut crosscountry directly to the destination.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2867

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5861&pm=2867

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Geometry