ShortCut | Topcoder Archive

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

```
{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.
```
{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.

{0,100,100,-100,-100,100}

{0,0,20,20,40,40}

Returns: 0.2962962962962963

{0,-100,-100,100,90}

{0,0,20,20,40}

Returns: 0.4585856530883108

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.