Connection Status:
Competition Arena > ShortCut

ShortCut

SRM 215 · 2004-10-16 · by lbackstrom

SRM 215 · 2004-10-16 · by lbackstrom · Dynamic Programming, Geometry
Class Name: ShortCut
Return Type: double
Method Name: suvTime
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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,10, 10,-40,-40,5, 5,150,150,160,160,150,150}
{0,  0,-10,-10,50,5,50, 50, 60, 60,-10,-10,  0}
Returns: 0.5840318810924577
3)
{0,10, 10,-40,-40,5, 5,150,150,160,160,150,150}
{0,  0,-10,-10,50,5,50, 50, 60, 60,  0,  0, 10}
Returns: 0.564350562948024
4)
{0,  0,-100,-100,100,100,-20,-20}
{0,-10, -10,   5,  5, 20, 20,  6}
Returns: 0.08810385239586963

Submissions are judged against all 33 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ShortCut with a public method double suvTime(vector<int> roadX, vector<int> roadY) · 33 test cases · 2 s / 256 MB per case

Submitting as anonymous