Statistics

Problem Statement for "ShortCut"

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

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

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

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

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

  5. {0, 0,-100,-100,100,100,-20,-20}

    {0,-10, -10, 5, 5, 20, 20, 6}

    Returns: 0.08810385239586963

  6. {0, 0,-100,-100,100,100,-100,-100,100,100,-20,-20}

    {0,-10, -10, 4, 4, 5, 5, 6, 6, 20, 20, 7}

    Returns: 0.03679765825083864

  7. {100,200,300,600}

    {0,600,200,1000}

    Returns: 0.7303017122985928

  8. {0,100,100,-100,-100,100}

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

    Returns: 0.2962962962962963

  9. {0,-100,-100,100,90}

    {0,0,20,20,40}

    Returns: 0.4585856530883108

  10. {0,5,10}

    {0,0,0}

    Returns: 1.0

  11. {900,200,-1000,400,400,612,-612,8,8,8,8,8,8,-8,2,1000}

    {900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915}

    Returns: 0.019702547674269585

  12. {900,200,-1000,400,400,612,-612,8,8,8,8,8,8,-8,2,1000}

    {19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4}

    Returns: 0.019702547674269585

  13. {900,200,-1000,400,400,612,-612,8,8,8,8,8,8,-8,2,1000}

    {190,180,170,160,150,140,130,120,110,100,90,80,70,60,50,40}

    Returns: 0.055766322383360566

  14. {90,20,-100,40,40,61,-61,8,8,8,8,8,8,-8,2,100}

    {190,180,170,160,150,140,130,120,110,100,90,80,70,60,50,40}

    Returns: 0.4071902740340737

  15. {456,529,102,936,803,461,678,-589,-511,-488,-995, -926,-395,-271,34,-147,604,650,427,274,452,842}

    {120,479,-547,-579,-97,-198,1000,-650,31,709,-325, -606,-873,-519,-267,-583,-964,-708,-702,-612,-648,-638}

    Returns: 0.13011156778959776

  16. {-213,954,841,965,-587,-357,-863,-189,-719,-657,-655,-899,-749,-581,-629,-757,-452,-393,-474,-656,-457,-546,-419,-437,-389,-452,-405,-378,-655,-851,-783,-732}

    {-173,-896,851,993,566,-233,446,-612,-397,-696,-720,323,997,475,330,352,22,-115,-36,175,-58,29,-108,-97,-143,-91,-150,-203,168,463,425,415}

    Returns: 0.08044387370908598

  17. {829,-271,955,178,983,972,53,853,-780,-543,-136,-647,-742,-906,-938,-766,-931,-799,-875,-902,-855,-897,-871}

    {413,-865,-56,-769,-367,193,-604,418,93,-614,-594,-999,-608,-466,-851,-669,-810,-565,-628,-496,-512,-517,-593}

    Returns: 0.20039704212064494

  18. {525,759,539,-659,333,618,-629,-88,230,-842,-108,47,-202,-30,-705,423,-550,523,500,942,858,692,232,232,534,333,684}

    {-188,78,-431,508,-767,-918,-337,-468,-671,680,786,430,540,582,643,54,448,-347,-199,614,-358,-646,-530,-196,-464,-554,-617}

    Returns: 0.04624404745551872

  19. {-97,-67,-739,-115,695,429,354,422,778,727,737,967,745,875,971,940,931,920}

    {-57,-529,-837,-877,-519,-249,211,534,845,-456,-354,447,-722,-208,197,-584,-166,-563}

    Returns: 0.20790849321517646

  20. {227,-583,-742,-536,-862,-996,-968,-957,15,583,-218,958,-531,386,-256,874,731,154,328,387,435,365,611,290,703,524,643,715,482,443,462}

    {-117,622,385,-922,-914,-448,-143,925,631,28,459,-784,292,-661,-896,-789,-672,-215,-587,-407,-558,-722,-706,-835,-747,-742,-694,-708,-508,-605,-692}

    Returns: 0.051342638051999616

  21. {-81,-929,-194,-86,-15,245,442,933,601,997,807,685,-762,524,75,-659,-399,-212,-5,-813,-1000,-717,-903,-873,-926,-883,-900,-996,-986,-870,-788,-884,-950,-923,-920,-881,-933,-995,-935,-938,-928,-900,-805,-992,-982,-944,-983}

    {557,-130,693,827,683,264,362,970,-351,725,-286,-681,-856,-350,83,-162,169,111,641,-299,-430,975,701,768,741,827,855,585,561,404,750,270,456,392,379,370,422,557,305,138,99,207,559,-329,224,-46,238}

    Returns: 0.06694236484403053

  22. {-255,-988,-610,122,-135,334,-540,993,176,441,845,841,729,898,904,-216,-120,521,279,393,139,773,-203,414,706,282,466,784,833,487,547,151,-152,75,790,477,246,95,-77}

    {699,642,315,-940,-341,-554,278,184,213,120,-815,-460,154,-566,-951,9,170,-391,-188,-348,-173,-672,23,-441,-633,-340,-462,-684,-885,-578,-623,-258,-29,-212,-852,-571,-357,-218,-86}

    Returns: 0.06860567931790991

  23. {703,-223,-398,-849,-540,-630,-480,391,-305,382,-162,-55,-529,-596,23,19,-338,-372,-124,-87,291,-202,-175,-271,-220,-121,-175,-207,-247,-188}

    {968,-877,-822,-666,38,-102,188,449,-348,407,-223,-278,-684,-480,330,130,-302,-420,-74,-48,388,-141,-120,-252,-206,-65,-136,-167,-227,-150}

    Returns: 0.12051170387732284

  24. {485,-137,-417,-209,787,181,449,968,-210,680,487,371,104,856,861,748,950,240,419,-328,-557,-692,-266,-840,-978,-801,-637,-402,-978,-458,-635,-595,-662,-923,-949,-806,-855,-823,-726,-923,-672,-784,-915,-759,-933}

    {957,185,663,-379,-883,130,169,746,47,891,549,501,296,701,811,720,987,1000,951,767,822,681,-568,776,156,11,-79,-980,-481,-887,-317,-377,-100,-304,-73,-88,-25,14,-98,-201,-94,-184,-208,-156,-206}

    Returns: 0.1125320727608943

  25. {0,7,2,1,-7,1}

    {0,-5,9,1,0,10}

    Returns: 0.34162599160153845

  26. {0,1,-7,1}

    {0,1,0,10}

    Returns: 0.8033541003199891

  27. {0,5,-5,5}

    {0,-1,-5,-10}

    Returns: 0.7602017877892847

  28. {0,-7,-8,-2,-4,-2,3,-4}

    {0,0,-7,-2,-2,-1,-10,-4}

    Returns: 0.23911583997851515

  29. {0,5,-9,1,-6,8,-10}

    {0,10,-6,3,-4,-8,-10}

    Returns: 0.2585980834405873

  30. {0,-6,8,-4,2,3,6}

    {0,-7,1,7,-2,3,0}

    Returns: 0.15375162069192738

  31. { 0, -100, -100, 100, 90 }

    { 0, 0, 20, 20, 40 }

    Returns: 0.4585856530883108

  32. { 0, 5, -5, 10, -10, 15, -15, 20, -20, 35, -35, 40, -40, 55, -55, 65, -65, 70, -70, 85, -85, 90, -90, 105, -105, 90, -80, 87, -98, 5, -5, 10, -10, 15, -15, 20, -20, 35, -35, 40, -40, 105, -105, 90, -80, 87, -98 }

    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50 }

    Returns: 0.03938143988910353

  33. { 0, 5, 5, -5, -5, -2 }

    { 0, 0, 1, 1, 5, 2 }

    Returns: 0.22539217924559546

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.
This problem was used for: