Statistics

Problem Statement for "BearCharges"

Problem Statement

Limak is a little bear who loves to play computer games. Today he is playing a game in which the goal is to capture all bases on the map.


There are N bases on the map. The bases are numbered 0 through N-1. For each i, base i is located at (x[i], y[i]). Initially, Limak only controls base 0.


Each base contains an electric cannon. The cannon in each base that is owned by Limak is being charged at the rate of 1 unit of energy per second. Charging happens continuously: for example, in 4.7 seconds the cannon gains 4.7 units of energy.


To capture an enemy base, Limak has to shoot it by a cannon from one of his bases. Shot takes no time but it consumes energy. Assume Limak wants to shoot base B using a cannon in his base A. Let D be the Euclidean distance between bases A and B. In order to shoot the cannon from base A to base B the cannon needs to have at least D units of energy. Exactly D units of energy are consumed by the shot. (I.e., at the moment of the shot the energy of the cannon in base A is decreased by D.)


At the beginning of the game the energy of the cannon in base 0 is 0. Whenever Limak captures another base, the energy of the cannon in that base is also 0, and the cannon begins to charge immediately after the capture.


Limak is able to fire the cannons at arbitrary, possibly non-integer times. He is able to fire multiple cannons at the same time. (Each of them pointed at a different enemy base.) Limak may capture the enemy bases in any order he likes.


Return the shortest time in which Limak can capture all the bases.

Definition

Class:
BearCharges
Method:
minTime
Parameters:
int[], int[]
Returns:
double
Method signature:
double minTime(int[] x, int[] y)
(be sure your method is public)

Notes

  • Your return value must have absolute or relative error smaller than 1e-9.

Constraints

  • N will be between 1 and 10, inclusive.
  • x will have exactly N elements.
  • y will have exactly N elements.
  • Each element in x and y will be betweeen -10^9 and 10^9, inclusive.
  • No two bases will be located at the same coordinates.

Examples

  1. {10, 11, 12}

    {0, 0, 1}

    Returns: 2.414213562373095

    Wait for one unit of time and then fire the cannon in base 0 at base 1 to capture it. Wait for another sqrt(2) units of time and then fire the cannon in base 1 to capture base 2.

  2. {0, 1, -2}

    {0, 0, 0}

    Returns: 3.0

    One possible strategy: After 1 unit of time base 0 captures base 1, and after another 2 units of time base 0 captures base 2.

  3. {0,0,0,-1,1}

    {1,0,-1,0,0}

    Returns: 3.0

    There are five bases. At the beginning Limak controls base 0 which is located at (0,1). After 1 second the cannon in base 0 has 1 unit of energy. At that point he can shoot the cannon to capture base 1, which is located at (0,0). After another sqrt(2) seconds the cannon in base 0 will have enough energy to shoot and capture base 4, which is located at (1,0). In the meantime the cannon in the newly captured base 1 is also being charged. One second after the capture of this base (i.e., 2 seconds after the game started) Limak can fire the cannon in base 1 to capture base 2. After another second he can fire the cannon in base 1 to capture base 3. At this moment, all the enemy bases have been captured.

  4. {-2,0,0,1,0}

    {0,1,-1,0,0}

    Returns: 4.23606797749979

    An optimal strategy: At time 2, base 0 captures base 4. At time 3, base 4 captures base 1. At time 4, base 4 captures base 3. At time 2+sqrt(5), base 0 captures base 2 and the game is over.

  5. {-500000000, -300000000, -100000000, 200000000, 300000000, 400000000, 600000000, 900000000, 950000000, 1000000000}

    {0,0,0,0,0,0,0,0,0,0}

    Returns: 1.5E9

    In this case, the optimal strategy is to use the cannon in base 0 to capture base 1, use that cannon to capture base 2, and so on.

  6. {0}

    {0}

    Returns: 0.0

  7. {-1000000000}

    {-1000000000}

    Returns: 0.0

  8. {-1000000000,1000000000}

    {1000000000,-1000000000}

    Returns: 2.82842712474619E9

  9. {17,200000000,30,450000000,700000000,-805123000,-100000000,-5000000,817000123,-500000000}

    {17,200000000,30,450000000,700000000,-805123000,-100000000,-5000000,817000123,-500000000}

    Returns: 1.1554126303654563E9

  10. {17,-100000000,817000123,-825924840,700000000,-5000000,200000000,-500000000,450000000,30}

    {17,-100000000,817000123,-825924840,700000000,-5000000,200000000,-500000000,450000000,30}

    Returns: 1.1680341342704592E9

  11. {9,2,10}

    {-6,10,-1}

    Returns: 18.70049002232823

  12. {9,4,-6,9,12}

    {-9,-7,-4,-11,12}

    Returns: 23.213203435596427

  13. {2,1,3,-2,-3,-1,-2,0,-3,-1}

    {-3,0,-1,3,-3,1,0,0,0,-1}

    Returns: 8.63441361516796

  14. {-68926616,-192280079}

    {696880327,404308132}

    Returns: 3.175130959837884E8

  15. {772574465,858030632,333073561}

    {-722939615,-239946253,301010289}

    Returns: 1.2442946454494705E9

  16. {367300984,105017235,480168068,943054987}

    {-656212366,-70392634,949600446,-943297310}

    Returns: 1.7286500556226134E9

  17. {-389887454,-96208532,-579622190,-863506681,993512613}

    {200591969,-282419706,115341625,840536237,963681985}

    Returns: 1.7879126805756063E9

  18. {162236012,-792284106,641492705,460288500,201963120,604521872}

    {-312878779,985596747,966540578,-825875044,803809041,-885851531}

    Returns: 2.5510544327620325E9

  19. {-381646699,-2893215,430910689,24348124,-6344404,-20129935,508013173}

    {-477104372,-954807376,796838524,-755145846,-910805388,-48361341,-939378260}

    Returns: 1.6705697432951016E9

  20. {-659350911,602706043,-683353808,-421882880,-19423407,441246334,-61852025,-598010065}

    {-746539379,-158023424,-213997410,569507294,-534147774,688112139,-571777587,-465145922}

    Returns: 1.985435251524928E9

  21. {-238981406,-568662164,345857912,-608951448,-727491851,295573252,-866099730,-188416496,620866679}

    {20932413,853257102,943663440,948721140,-683416594,-830616793,417150783,190264522,422714686}

    Returns: 2.0211742658530502E9

  22. {119,529,654,-18,943,716,-994,-538,629,403}

    {935,618,-940,-202,107,513,510,-996,592,-497}

    Returns: 2556.3892352869707

  23. {496,-362,389,80,-470,-527,714,-477,-523,-651}

    {-499,-462,818,768,-124,-116,-346,883,650,-58}

    Returns: 2315.876391626331

  24. {-854,-80,947,-369,-395,153,154,-789,-412,-603}

    {-85,743,974,-88,-424,393,-660,651,-516,371}

    Returns: 2178.69806358825

  25. {450,-214,-584,675,427,-704,355,-209,-636,-926}

    {276,-84,551,-690,759,673,-120,-25,787,621}

    Returns: 1785.681425147769

  26. {176,434,205,-661,628,511,-896,-53,681,-8}

    {244,667,471,-252,-846,723,560,-432,496,-792}

    Returns: 1939.4662366049804

  27. {914,-75,-70,908,-297,264,613,-456,827,-420}

    {-208,172,119,99,582,350,372,829,743,-331}

    Returns: 1959.519822736023

  28. {219,490,824,-484,172,139,-113,-674,183,87}

    {527,-246,-606,629,250,-352,-451,-597,-39,475}

    Returns: 1573.3853610523188

  29. {684,991,-881,-86,-397,-114,430,-546,863,894}

    {-308,274,725,954,-509,-172,-27,294,787,218}

    Returns: 2123.094271531469

  30. {3,-515,96,-63,629,695,-392,353,-483,755}

    {921,-762,422,691,116,693,-826,-931,78,-827}

    Returns: 2226.2563986532896

  31. {40,802,979,-796,549,849,809,159,310,352}

    {-260,84,411,90,-144,878,-592,767,-382,298}

    Returns: 1830.5286251638681

  32. {79323627,910782199,-433066925,-243883391,-691574290,-509003036,-510663622,-255111770,-307783771,272682211}

    {-804736548,-645773706,46453063,-854356699,423894023,-580738708,546190790,-50543390,430981232,-573472134}

    Returns: 1.8344517970792017E9

  33. {-2207097,-721901275,163695385,473008852,-727604888,588495093,64587483,238021678,-28662506,-336844043}

    {-320956218,851127613,-123801764,273163351,173662052,-605634013,-815779190,143004029,701299897,253069616}

    Returns: 1.6334109851726825E9

  34. {384071803,4880276,549490933,-543557951,255330041,-962343240,241958488,-591309041,-52019466,-917890622}

    {-432390507,674523415,926210259,397795313,-249829778,757117936,-405334485,210405062,235274521,-826563648}

    Returns: 1.8671819431801388E9

  35. {133113521,-723471800,742636618,654359915,986726979,-873324739,998033470,747476355,-98156841,405375835}

    {-400418322,-194169552,232057892,176332405,567167634,-886152398,391462475,40796099,-801517982,825611565}

    Returns: 2.0274634467954583E9

  36. {-538256567,-965463244,-668712935,903097833,22032057,124371138,636994788,92300879,-865827062,763920014}

    {125380799,869789284,462501077,-877770670,87920092,631680460,-408940164,898980080,365148780,146064046}

    Returns: 2.096303036831942E9

  37. {-998901964,852816391,-893649987,-218240447,798570279,980621934,-496992012,797121469,-249801469,-901814943}

    {-955973645,668731568,92252553,-135989198,66927902,-944722094,-625058673,-244960551,-637892602,9867344}

    Returns: 2.6912774152960014E9

  38. {295902028,379923744,710927939,-316727829,736129793,-203685776,72452893,491843550,797148432,-273264856}

    {736813059,-840710122,559516923,564949146,52226968,407959627,-904718603,290006657,824675006,126678859}

    Returns: 1.9650275988356676E9

  39. {734239706,569697539,-268040826,992383310,494427367,603855613,88082312,-552461327,-819907859,-202489833}

    {-300485447,180048123,-619554211,322565666,840225556,-104567772,301807987,-758517159,580473372,102837923}

    Returns: 1.9685538043492718E9

  40. {-190507664,-40708242,194340385,-906905775,-927369916,503335141,498274335,-243670641,324112604,-840309218}

    {891761539,138488377,8607759,-191958004,317001107,-912951463,-217785506,122531872,-644890821,-122169158}

    Returns: 2.0252835439628022E9

  41. {-562502250,-308335712,124702390,10521218,-780850041,297067734,-736722771,418824774,180798643,-400979622}

    {622044244,379975182,-540336430,788217690,349774573,648863680,131603230,-950582349,-481768983,-342866634}

    Returns: 1.9277670773024127E9

  42. {223051464,-587072936,-742265726,484955401,412406631,-282087500,-354256877,-312547163,-750130100,-362780644}

    {406672677,-882789572,-961865082,-198930445,879754889,-596180914,335679243,452239449,-185474533,-462051806}

    Returns: 2.0338929085416536E9

  43. {53611041,-641104306,-333615092,-49590477,621560860,-869556663,410979931,-3724082,-450254573,-44641240}

    {-924937282,-209990656,193644371,-26155484,-343857851,68650172,-880218918,-751842034,475419553,-141978297}

    Returns: 1.541427503406181E9

  44. {-927014014,968137983,-533506257,75350453,148302932,-974858199,-6235611,154566181,-629658630,-775179088}

    {-726320738,396084807,455824590,-951606392,-746790329,-157471745,589501123,804898798,71825477,631683023}

    Returns: 2.6156401463899603E9

  45. {-62401301,545883870,-397758895,661748870,636849111,853135897,-490725406,-266436302,-139413669,843380168}

    {17931575,-418271206,-538241383,412094007,-942653909,-554185351,-513586118,-684110305,-693192005,100424785}

    Returns: 1.9753128052744598E9

  46. {300516412,818836128,785328556,180477653,-600410145,449072970,110839114,-325630566,559831062,951915404}

    {508362608,-820032894,460919553,594033090,-45207278,811296824,-245863229,-26757781,434057449,230762595}

    Returns: 1.5503075155601594E9

  47. {29321543,63545593,-51292176,-326778710,-36391691,-714206080,-838115940,-772995537,611281316,-655703493}

    {482889146,-8507443,434692199,-793259056,574654942,-173059176,556943539,640012629,-608657475,-554662145}

    Returns: 1.5316915644394617E9

  48. {-160734018,660850870,135601889,-47029005,-841563682,434753888,417574497,-481030874,535033090,988846589}

    {114140869,272358942,203418748,-897050276,-48828838,551663904,-152765543,170390081,576083300,-8123790}

    Returns: 1.652254754033533E9

  49. {639017232,-77537003,-437827629,-303521963,75883702,393385834,650533716,583551863,350684908,205038620}

    {-900613268,-164150750,-66214209,-687909074,-25093494,-160285547,812096420,-720943923,362442649,-26862427}

    Returns: 1.8449971765845237E9

  50. {524282478,936635969,965363849,781356880,-541193691,514551654,-377675831,-297588987,72708982,-302866959}

    {-153531855,-90491213,541998148,818462649,15050017,-139330413,390019759,876308131,509733375,308833005}

    Returns: 1.5526664928075874E9

  51. {-438949302,77567664,-871294434,-898849519,-27838149,-751554452,790964783,-989690363,-477358063,91029873}

    {-852386951,-638884114,-343950620,-237213894,451290143,-404930485,815030213,488565351,-551623323,446773541}

    Returns: 2.203923486054119E9

  52. {-742451027,-742254296,500441747,135021918,500373499,134513778,501263380,-741919980,135425581,499994099}

    {-804625298,-803785724,776647214,-372505829,775547995,-372972807,775369212,-803981807,-373354578,776048027}

    Returns: 2.0117100584154425E9

  53. {-377516361,-945401011,-695508615,-695383401,-377980923,-944469639,-377981963,-945667503,-695944528,-695420157}

    {-816881106,-691405338,-814015431,-814282642,-817122003,-691195035,-817423418,-692746488,-815069979,-814482361}

    Returns: 5.820958932698567E8

  54. {204825730,749029267,749634895,310030849,204358804,749898009,310245107,309775349,749257390,203418501}

    {-681446205,47797435,47989888,691707501,-682534224,49355067,690772869,691191010,49188365,-682192646}

    Returns: 1.3786515965039442E9

  55. {170064660,170064669,641292349,325598476,325598537,641292374,641292266,325598385,641292201,325598392}

    {582751835,582751942,-456567929,-313540244,-313540279,-456567950,-456567934,-313540372,-456567925,-313540230}

    Returns: 1.1411580162500567E9

  56. {685506370,830188352,830188438,109010409,109010434,685506507,830188454,830188425,109010303,109010304}

    {-696257276,-425733824,-425733692,-36427520,-36427562,-696257178,-425733720,-425733668,-36427693,-36427581}

    Returns: 8.761983343886572E8

  57. {660117542,-923911975,-510039665,-510039606,-923912077,660117537,-510039700,-923912076,-923911987,-510039679}

    {-916337208,375387029,310373435,310373491,375387040,-916337328,310373522,375387097,375387021,310373562}

    Returns: 2.0439427691427643E9

  58. {410803427,-664546674,-665757851,981537952,397860778,982414353,982876302,982775814,-664543672,399050851}

    {-624426166,-268827605,-269423055,-479711362,-278302623,-480168019,-478870230,-479361797,-268611249,-278399752}

    Returns: 1.4103801039234047E9

  59. {176522754,-596617505,-257295711,-258283563,-595342652,-257102166,-595858785,4671765,4974597,-258420145}

    {-126280033,161936170,776982941,776291296,161570280,775827750,160110775,-70840790,-70186939,775480684}

    Returns: 1.0683002618131627E9

  60. {-691734867,-170146742,607290606,605978160,-170294084,-774143420,606555587,-170913465,607409812,-774819296}

    {-993523305,750476996,126666701,125489862,750802245,242103563,126700611,750656714,125222534,243651545}

    Returns: 2.6277593389623756E9

  61. {-713914695,749734031,749559359,750364920,925056033,-162709308,-161880730,749604098,925487198,-161737904}

    {-180698713,208685816,207968565,208879122,994869395,-616042534,-617830259,209189772,993239919,-616393793}

    Returns: 2.319783916453572E9

  62. {-975898812,-810765349,-411935895,-175318287,-175414590,-412287572,-809169622,-412548435,-175665755,-412425362}

    {-802821152,-387845251,348487226,336974939,335698171,347542951,-388094127,348292841,335840951,347800087}

    Returns: 1.4116970314288936E9

  63. {-296044842,-907332076,236268846,-935701931,-353282338,236427135,-139505904,-199630156,-886836196,279818520}

    {862149735,-1000000000,-437113709,-959509189,848677368,-506280483,-834631643,-873448802,-1000000000,-482805535}

    Returns: 2.1027550140963871E9

  64. {989871252,218756334,168942528,824211608,-100162145,914720380,-67399530,837494258,229457027,-55678833}

    {913010883,465036065,478463731,820166256,178437665,904905965,245748204,876468830,522609929,170780102}

    Returns: 1.3375296787434235E9

  65. {113873069,-455916875,-968251282,168170160,-484520342,-186436978,-515164095,-950550986,-177438817,-268632859}

    {-64126640,-269085005,-740030176,-67547851,-207627617,417433434,-274533637,-788142361,467642706,447242294}

    Returns: 1.3658897059783053E9

  66. {-877271623,-261934865,-254245893,-211378308,170109150,-253340624,173548838,-243567077,-251701015,-843588679}

    {-143610932,69214571,59460038,-816095892,133609417,-846761200,84741029,6644325,-821706351,-144585963}

    Returns: 1.1431524280527818E9

  67. {-46943079,-546618000,-617131754,-901500251,-987774973,-962609062,-572515414,-24160722,-497430258,-629799917}

    {-825128102,-373137097,-235209154,804004278,747374190,779338680,-439035628,-804796538,-412857375,-185793395}

    Returns: 1.9220889932567337E9

  68. {626564337,727187065,-377760492,383481452,934825348,383482282,-377760902,934824910,923182135,727185914}

    {-347533726,-497140056,956320732,111808811,-60231364,111808139,956319911,-60230926,-870539362,-497139824}

    Returns: 1.6566625893435066E9

  69. {-370985499,-612856036,310157461,-612855341,310156280,-930213261,508464952,508463459,-374750084,-374751629}

    {786855051,472338363,755725369,472338487,755725334,566945074,916220682,916221143,924308833,924310123}

    Returns: 1.0207574593135614E9

  70. {656108679,191974260,124497362,967464077,-165870667,134955809,967464069,124497110,134955852,191975111}

    {72837161,-923478136,267599732,-244181517,-991425908,-36128824,-244181234,267599069,-36128534,-923478910}

    Returns: 1.542933475628012E9

  71. {-369228352,973731779,405295112,973732186,-104856972,-8453994,405293396,-8453649,331161947,331160863}

    {380050418,-260121258,955480155,-260119780,-329439269,-776635736,955480180,-776635573,515937792,515936275}

    Returns: 1.9280635664381378E9

  72. {-715123580,-752123317,-434475752,416712772,-513043537,-513044422,-752122330,416711443,-434476221,-633150042}

    {-660951623,720442821,444721612,545785629,220010797,220010019,720442715,545786370,444722924,-538376398}

    Returns: 1.6566391028752313E9

  73. {-1000000000,1000000000,374561004,-1000000000,1000000000,-477248830,-440143410,410339460,-538431186,-251280099}

    {-1000000000,1000000000,-108755237,1000000000,-1000000000,89875164,-414643200,-359022689,-406793869,-441455542}

    Returns: 2.8689446357300034E9

  74. {-1000000000,575916829,-793845391,1000000000,143867946,-636997997,-506166840,581139521,1000000000,-1000000000}

    {-1000000000,-633022978,871347528,-1000000000,-49941076,547159417,825701388,576315198,1000000000,1000000000}

    Returns: 3.608230026132286E9

  75. {-1000000000,1000000000,202716986,930629716,677509330,-299668615,563690828,1000000000,-252462830,-1000000000}

    {-1000000000,-1000000000,-551588923,-769786740,594499381,-339174716,522489675,1000000000,-372930897,1000000000}

    Returns: 2.9628884176215324E9

  76. {-1000000000,-599815301,-174980002,-943679693,-1000000000,130950205,-571027567,1000000000,559928772,1000000000}

    {-1000000000,-99757829,-191778233,184114713,1000000000,-314987139,182577546,1000000000,459938516,-1000000000}

    Returns: 3.0399435070492325E9

  77. {-1000000000,388165214,1000000000,-519782514,429415835,-1000000000,-23146973,1000000000,-81949754,-478816343}

    {-1000000000,-560916643,1000000000,-820609847,-278568751,1000000000,-943396301,-1000000000,367306957,627897495}

    Returns: 3.1424408708718047E9

  78. {80, 87, 64, 27, 31, 93 }

    {22, 27, 7, 55, 76, 14 }

    Returns: 86.30062790466825

  79. {18, 19, 4, 0, 7, 17, 10, 16, 2, 19 }

    {9, 9, 12, 8, 8, 3, 7, 14, 11, 1 }

    Returns: 20.041594578792296

  80. {0 }

    {0 }

    Returns: 0.0

  81. {-500000000, -300000000, -100000000, 200000000, 300000000, 400000000, 600000000, 900000000, 950000000, 1000000000 }

    {1000000000, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 1.9806248474865696E9

  82. {-49070709, 32966494, -11762230, -28838758, -8928056, 38918848, -43689199, -19314809, -39885608, -32899257 }

    {-42359681, -47935890, -34665989, -38430201, -43592745, 32926484, -42228952, -17888102, -39713940, -25042965 }

    Returns: 1.1598817610000287E8

  83. {8, 8, 9, 6, 2, 8, 6 }

    {3, 6, 8, 6, 3, 2, 2 }

    Returns: 7.35917360311745

  84. {45087933, -49595556, 23120487, -38881331, -42898858, 26943367, -46826227, -4567741 }

    {23145806, 11459153, 38487204, 12670232, 9093255, 49087468, 23720408, -18730030 }

    Returns: 1.1294521065636271E8

  85. {2, 12, 1, 18, 7, 11, 9, 7, 15, 3 }

    {13, 2, 16, 15, 6, 18, 12, 19, 14, 11 }

    Returns: 19.26933802766729

  86. {0, -6, -3, -1, 5, 5, 8, 8, 10, 11 }

    {0, 0, 0, 0, 0, 3, 0, 1, 0, 0 }

    Returns: 11.0

  87. {0, 0, 0, 1, 1, 1, 2, 2, 2, 99999999 }

    {0, 1, 2, 0, 1, 2, 0, 1, 2, 99999999 }

    Returns: 1.4142135482309595E8

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: