TopCoder Statistics - Problem Statement

Problem Statement

Your friend is going to the mountains on vacation. He will climb up and down several mountains, and he has asked you to calculate his total walking distance.

To simplify this task, everything will be represented on a 2-dimensional cartesian plane. The ground is represented as the x-axis, and the mountains are represented as the union of several isosceles triangles. You are given int[]s start and finish. For each index i, construct an isosceles right triangle with its hypotenuse lying on the ground from point start[i] to point finish[i].

The mountains are guaranteed to form a single connected non-degenerate polygon, where the height is positive everywhere between the start and end points. The path your friend will walk is defined as the upper part of this mountain, shown in bold in the figure above. Return the length of this path.

Definition

Class:: MountainRoad
Method:: findDistance
Parameters:: int[], int[]
Returns:: double
Method signature:: double findDistance(int[] start, int[] finish)
(be sure your method is public)

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.
An isosceles right triangle is a triangle with angles 90, 45 and 45 degrees. The hypotenuse of such a triangle is the side opposite the 90 degree angle.

Constraints

start will contain between 1 and 50 elements, inclusive.
start and finish will contain the same number of elements.
Each element of start and finish will be between -1000 and 1000, inclusive.
For every i start[i] will be strictly less than finish[i].
The union of the isosceles triangles described in start and finish will be a single connected nondegenerate polygon.

Examples

{1}

{7}

Returns: 8.485281374238571

In this case there is only one mountain.
{0,3,4}

{5,9,6}

Returns: 12.727922061357857

This situation with three mountains is shown in the figure above.
{1,4,5,6,-10}

{101,102,101,100,99}

Returns: 158.39191898578665
{-5,-3}

{-2,-2}

Returns: 4.242640687119286
{0,1,2,3,4,5,6,7,8,9,10,11}

{12,12,12,12,12,12,12,12,12,12,12,12}

Returns: 16.970562748477143
{0,4,8,0}

{4,8,12,12}

Returns: 16.970562748477143
{0,1,2,3,4}

{10,9,8,7,6}

Returns: 14.142135623730951
{0,0,0}

{4,8,12}

Returns: 16.970562748477143
{0,2,2}

{4,4,6}

Returns: 8.485281374238571
{0,0,6,7,8,15}

{4,10,22,23,24,24}

Returns: 33.941125496954285
{0,0,8,0,4,8,12,0,2,4,6,8,10,12,14}

{16,8,16,4,8,12,16,2,4,6,8,10,12,14,16}

Returns: 22.627416997969522
{-7,1,-5,-4,-1,-3}

{2,3,0,-3,6,2}

Returns: 18.38477631085024
{5,6,-16,-7,-7,-13,-18,-13,-18,-12}

{15,15,0,20,2,12,11,11,-11,-5}

Returns: 53.74011537017761
{2,-18,-13,-10,-12,5,-12,7,3,-18}

{3,2,6,5,-7,11,7,11,15,9}

Returns: 46.66904755831214
{0,1,-10,-9,-6,8,9,-7,15,-10}

{6,10,11,15,13,10,14,16,16,-8}

Returns: 36.76955262170048
{-9,-8,-19,-19,-4,-18,-13,-13,-18,-10}

{-4,14,-8,-8,16,17,16,-4,9,-4}

Returns: 50.91168824543143
{-17,-8,7,-11,-4,-14,16,-20,-20,-8}

{10,3,10,-1,18,15,19,10,-17,10}

Returns: 55.15432893255071
{107,100,104,100,107,100,104,104,101,104,102,105,100,108,105,103,106,100,104,105}

{110,105,106,103,110,107,110,107,106,106,105,109,101,109,109,107,110,105,105,107}

Returns: 14.142135623730951
{104,100,108,104,102,100,103,100,103,101,102,101,105,101,102,100,105,102,104,102}

{108,108,110,107,105,107,109,102,107,106,104,110,109,103,109,107,109,103,109,110}

Returns: 14.142135623730951
{105,102,102,105,101,101,105,103,101,100,104,101,103,103,106,101,102,102,106,105}

{106,109,110,108,102,107,108,104,107,106,110,105,110,106,107,103,103,104,108,107}

Returns: 14.142135623730951
{103,102,106,105,101,104,105,103,109,101,101,101,101,102,105,101,104,105,101,101}

{106,104,110,110,104,107,109,109,110,110,109,103,108,103,106,103,105,108,110,106}

Returns: 12.727922061357857
{101,100,105,106,101,101,100,103,102,106,104,102,104,104,102,104,105,105,100,102}

{107,107,107,107,106,106,107,110,103,109,108,108,107,106,104,107,108,106,109,110}

Returns: 14.142135623730951
{-960,-965,-929,-979,-976,-964,-959,-942,-963,-938,-925,-988,-971,-967,-971,-991,-931,-965,-949,-995,-932,-972,-984,-978,-917,-947,-949,-995,-995,-979}

{-934,-955,-903,-937,-934,-926,-904,-904,-931,-935,-920,-980,-960,-945,-954,-936,-903,-948,-937,-945,-927,-936,-931,-938,-900,-929,-926,-967,-976,-962}

Returns: 134.35028842544403
{-989,-993,-959,-969,-998,-949,-994,-995,-996,-980,-966,-998,-931,-928,-990,-936,-947,-970,-964,-991,-998,-960,-995,-923,-989,-963,-990,-991,-968,-978}

{-967,-945,-954,-910,-948,-947,-922,-919,-954,-974,-939,-982,-912,-921,-940,-914,-933,-927,-940,-945,-910,-945,-985,-911,-939,-924,-982,-986,-922,-977}

Returns: 124.45079348883237
{-953,-956,-969,-956,-959,-967,-926,-961,-997,-993,-975,-965,-976,-956,-996,-971,-997,-961,-986,-941,-932,-990,-966,-946,-935,-992,-975,-978,-970,-941}

{-923,-929,-950,-911,-911,-933,-918,-932,-962,-950,-932,-950,-940,-921,-965,-968,-971,-947,-967,-939,-922,-983,-924,-938,-934,-961,-974,-964,-914,-925}

Returns: 121.62236636408618
{-991,-947,-969,-987,-964,-996,-991,-910,-944,-975,-981,-947,-947,-921,-981,-973,-946,-960,-967,-990,-988,-982,-934,-976,-986,-994,-974,-974,-974,-976}

{-963,-936,-916,-924,-951,-932,-908,-902,-907,-947,-917,-925,-917,-912,-915,-922,-934,-940,-923,-987,-984,-933,-922,-918,-942,-968,-951,-920,-921,-916}

Returns: 132.93607486307096
{-956,-992,-956,-983,-958,-981,-989,-964,-989,-990,-995,-954,-986,-994,-953,-949,-972,-997,-992,-975,-977,-992,-981,-975,-965,-999,-996,-993,-967,-962}

{-912,-916,-922,-915,-939,-952,-979,-929,-959,-947,-915,-933,-970,-989,-949,-915,-931,-948,-969,-911,-933,-927,-919,-946,-947,-992,-970,-944,-931,-960}

Returns: 124.45079348883237
{901,901,902,903,900,904,900,905,904,900,905,900,901,905,902,903,906,901,907,901,906,900,901,907,901,907,901,905,901,905,906,903,901,903,907,901,900,900,903,904,900,901,900,905,905,904,906,901,903,901}

{909,907,909,907,907,909,908,906,906,906,907,904,909,909,909,905,909,903,908,903,908,902,908,908,906,909,903,907,902,908,909,907,905,909,909,904,908,904,906,907,906,908,902,908,908,908,908,906,906,903}

Returns: 12.727922061357857
{900,902,900,903,903,901,906,900,902,903,902,903,902,901,900,902,900,905,904,905,904,903,900,908,908,904,901,901,901,901,904,901,907,904,902,904,901,907,904,902,904,905,903,900,901,903,902,906,903,906}

{908,907,902,905,905,905,907,907,905,909,903,904,903,905,906,909,902,908,909,909,907,908,902,909,909,909,904,903,907,907,907,903,909,907,908,906,906,908,906,906,905,906,907,906,903,905,908,909,907,909}

Returns: 12.727922061357857
{903,903,906,904,902,901,902,904,901,904,900,906,902,903,901,905,903,904,901,905,907,907,901,907,903,904,906,903,902,902,900,905,902,902,901,905,904,904,902,902,901,906,900,902,902,902,904,904,904,901}

{905,909,908,908,904,905,904,909,903,906,907,908,909,904,904,908,908,907,904,906,909,909,906,909,907,909,908,905,909,905,902,908,908,905,909,909,909,907,903,905,906,909,908,909,909,903,907,906,909,904}

Returns: 12.727922061357857
{902,900,906,903,908,905,900,901,907,905,903,904,904,904,901,901,904,907,904,902,902,902,902,904,907,901,902,902,900,900,905,900,908,906,900,904,900,904,906,904,904,902,904,904,903,904,901,902,900,900}

{909,909,909,906,909,906,902,907,909,907,905,905,909,906,907,905,905,908,905,909,906,909,909,907,908,905,906,903,908,905,906,904,909,908,903,907,902,909,907,907,905,903,907,907,907,909,907,908,906,904}

Returns: 12.727922061357857
{902,908,901,901,904,903,900,900,906,904,900,902,902,900,902,906,902,901,904,901,900,905,903,905,905,901,902,900,901,901,904,900,905,902,901,900,903,902,902,900,900,906,901,904,900,901,907,902,900,903}

{906,909,909,906,906,906,906,904,907,906,903,905,906,909,907,909,909,902,909,907,905,909,905,909,909,906,906,901,908,909,905,907,906,905,908,905,907,903,909,901,904,907,909,909,908,903,908,909,909,909}

Returns: 12.727922061357857
{-304}

{751}

Returns: 1491.9953083036153
{-938}

{-859}

Returns: 111.72287142747452
{-413,-386,-825}

{521,28,951}

Returns: 2511.643286774617
{-658,161,-433}

{781,667,348}

Returns: 2035.0533162548838
{-306,46,559}

{749,898,796}

Returns: 1702.7131290972065
{-206,867,80}

{304,990,950}

Returns: 1691.3994205982217
{-668,-225,-279}

{366,156,609}

Returns: 1805.9507191504424
{329,-921,-491,-73,381,-943,-666,-269,-944,-764,-428,-208,671,-743,155,9,-662,-495,-508,-623,-591,-352,487,243,-692,338,-537,50,-945,289,-930,-573,-900,33,-617,-824,705,-377,-657,-351,-718,-552,-815,361,-276,-887,-218,-179,-493,492}

{431,-570,827,906,815,-500,-593,80,-326,861,517,11,862,34,808,478,936,818,-443,305,-454,-223,851,339,326,786,472,755,-695,628,440,296,-403,644,-488,772,811,150,-21,-64,-382,-26,-96,620,-196,-722,-11,343,597,591}

Returns: 2660.135710823792
{355,-425,-704,-698,615,-534,837,-215,104,-211,135,-976,-376,215,-447,-223,-874,-871,-603,103,-850,-631,14,-63,499,-931,-623,-896,-318,231,-927,-941,195,-240,-948,-102,-590,-813,-45,-538,-780,-924,-151,329,-346,-674,-82,239,218,-822}

{950,-388,624,381,965,984,894,527,876,86,892,779,531,647,814,247,-394,-788,-205,139,775,129,987,213,837,437,-226,860,-48,263,-671,919,303,696,120,173,-12,-258,478,548,273,192,470,683,323,591,153,750,556,44}

Returns: 2776.101222938386
{-362,-834,-564,-591,-940,-501,-380,-565,-321,-757,-823,-660,-847,-818,-227,-941,-787,-817,-801,-879,-733,517,81,-599,-647,78,241,-796,61,-679,-523,-947,-630,-892,-923,-962,-943,303,-135,-574,-377,-188,-966,-703,-469,-151,-700,141,-499,585}

{-238,-626,899,719,-505,309,19,597,772,-177,-358,252,-581,-719,-58,-251,617,681,60,-443,483,771,840,-20,66,637,348,-631,845,-12,-311,-8,164,-303,-642,349,413,883,177,694,28,806,-522,856,539,388,-646,491,411,812}

Returns: 2637.5082938258224
{26,102,-380,-371,-469,93,-977,-398,-636,-157,-616,-351,-26,-329,-948,-929,-632,-551,-248,-773,-884,251,344,-537,217,-838,-676,-803,-971,-533,-899,352,833,-506,-257,461,-776,-290,-724,-139,-817,563,-888,-315,750,-965,-941,226,-693,-847}

{491,732,-100,165,-404,208,-685,276,837,841,704,753,447,138,9,672,732,476,581,-533,862,759,825,923,774,650,417,-529,-394,768,448,854,938,151,-112,533,602,188,124,272,-673,736,397,326,814,537,-42,598,730,-379}

Returns: 2708.2189719444773
{-717,-737,252,-449,-949,-693,601,129,-262,-979,-827,-466,735,318,-275,-882,-121,-857,-151,-850,546,-739,-927,-812,-541,838,371,-631,152,-665,-364,188,-309,-732,-276,269,-817,-978,-102,-964,399,147,-644,-545,-713,-161,-600,159,-896,-454}

{840,286,287,268,504,395,787,305,235,-157,-144,-463,924,817,289,-862,228,968,891,-210,660,425,-296,921,-340,854,423,62,377,51,400,647,-294,801,589,594,598,744,191,490,764,758,-55,91,-680,331,613,345,-258,322}

Returns: 2753.4738059404162
{-862,-570,-528,-960,-352,736,411,-877,257,-232,187,-970,-810,-747,-940,-326,525,-261,-763,-54,-380,15,-495,-234,-452,264,57,-227,-832,-804,-361,-951,-105,-431,141,-816,-168,503,-135,-387,4,263,-372,-835,-188,-789,-93,206,-774,5}

{-372,-462,-470,499,676,928,977,-79,904,-1,429,-151,968,178,-35,292,538,67,-15,972,661,483,774,-125,332,990,763,733,97,-720,25,282,77,636,430,-707,474,953,225,571,352,983,774,389,537,998,553,890,-609,766}

Returns: 2783.1722907502512
{-756,-622,-413,-645,-249,-778,-622,780,-117,85,160,-961,-330,-733,-315,352,-471,-248,-538,360,822,-550,-702,-962,-762,18,-304,-982,-322,-553,-561,-512,-62,-814,-778,-439,-609,426,-392,-691,478,-472,-78,212,-266,-927,-906,-461,-990,-940}

{-180,-309,-26,342,141,271,126,831,818,115,479,-432,-259,427,648,533,651,244,-282,409,844,-342,808,415,517,718,12,-403,448,392,-336,614,753,-621,14,-383,-263,611,453,-162,742,380,617,467,37,161,-573,566,-962,534}

Returns: 2593.6676733922563
{-981,-164,-477,61,-854,-542,-400,-825,-952,-202,-982,718,-133,-320,-781,114,-180,-404,-945,-476,-26,-548,-472,41,-12,-971,405,883,-354,-869,-628,-489,160,-930,-996,-956,-667,-423,-876,-792,-868,-243,-383,-915,228,-23,-430,-222,-120,-865}

{-956,972,-156,73,805,39,705,19,569,879,684,731,619,895,891,344,940,-292,-730,68,348,120,196,179,563,-177,654,962,123,313,914,499,233,588,20,-911,851,-213,-413,63,740,-23,927,-250,684,868,-136,73,745,552}

Returns: 2783.1722907502512
{-387,-26,-199,-155,-319,-373,-421,355,-957,560,-959,854,-466,573,-594,-681,-810,-941,-420,-690,-835,651,-467,-737,-703,-24,-197,230,-891,-637,-52,-828,-125,-709,-831,112,-422,180,-860,-34,-885,-450,-419,-512,-115,-594,558,-225,-688,-835}

{243,297,905,376,320,319,52,490,-377,819,-748,863,238,637,-342,-68,201,-7,642,219,826,880,215,-383,625,953,109,395,-578,720,-2,-632,249,169,-819,877,490,553,-602,538,145,372,188,883,467,-396,654,829,-468,571}

Returns: 2703.9763312573577
{337,-608,-574,-801,150,-362,-666,-866,-410,-887,-861,181,626,-505,-791,-481,-147,-237,-907,-701,118,-72,332,-863,-692,-251,-570,-888,-909,-579,-509,-561,-562,94,-719,-439,-599,-471,-736,-309,-723,-624,-446,-290,-59,-912,-644,-293,-892,-858}

{576,-274,435,932,752,126,763,617,-140,-881,279,213,999,290,-605,398,168,-31,600,120,897,30,830,982,613,-5,-65,-749,-632,-267,766,237,725,219,-195,578,-270,93,963,213,90,892,685,703,867,108,461,-35,-236,-648}

Returns: 2702.562117694985
{-1000}

{1000}

Returns: 2828.42712474619
{-900}

{-899}

Returns: 1.4142135623730951
{900}

{901}

Returns: 1.4142135623730951
{-5, -3 }

{-2, -2 }

Returns: 4.242640687119286
{1, 4, 5, 6, -10 }

{101, 102, 101, 100, 99 }

Returns: 158.39191898578665
{0, 3, 4 }

{5, 9, 6 }

Returns: 12.727922061357857
{1 }

{7 }

Returns: 8.485281374238571
{1, 4, 5, 6, -10, -100 }

{101, 102, 101, 100, 99, 2 }

Returns: 285.67113959936523
{1, 2, 3, 4 }

{8, 7, 6, 5 }

Returns: 9.899494936611665
{1, 5, -1 }

{6, 6, 2 }

Returns: 9.899494936611665
{1, 4, 5, -6, -10 }

{101, 102, 101, 97, 99 }

Returns: 158.39191898578665
{-1 }

{1 }

Returns: 2.8284271247461903
{1, 2, 4 }

{6, 3, 5 }

Returns: 7.0710678118654755
{1, 2 }

{4, 3 }

Returns: 4.242640687119286
{-1000, -1000 }

{1000, 1000 }

Returns: 2828.42712474619
{1, 2, 3 }

{998, 999, 1000 }

Returns: 1412.799348810722
{0, 1, -2, 5 }

{6, 15, 3, 1000 }

Returns: 1417.0419894978413
{-1, 3, 1, 5, 2, 3, -2 }

{4, 11, 9, 11, 10, 7, 0 }

Returns: 18.38477631085024
{-10 }

{-1 }

Returns: 12.727922061357857
{1, 4, 5, 6, -10, -1, 5, 8, 3, 6, 8, 9, 4, 3, 2, 43, 3, 2, 1, 6 }

{234, 132, 41, 241, 234, 123, 42, 44, 23, 23, 42, 34, 123, 41, 234, 534, 1000, 234, 234, 333 }

Returns: 1428.3556979968262
{1, 2, 3, 5 }

{6, 4, 7, 8 }

Returns: 9.899494936611665
{0, 3, 4, 7 }

{5, 9, 6, 8 }

Returns: 12.727922061357857
{0, 3, 1 }

{2, 5, 4 }

Returns: 7.0710678118654755
{0, 0, -1000, -1000, -1000, 0, -1, -2, -1000 }

{1, 1, 0, 0, -1, 777, 5, 3, 1 }

Returns: 2513.05750033699
{0, 1, 3 }

{5, 2, 4 }

Returns: 7.0710678118654755

Statistics

Problem Statement for "MountainRoad"

Problem Statement

Definition

Notes

Constraints

Examples