Statistics

Problem Statement for "PointsGame"

Problem Statement

You are given a set of white points on a plane, with the x and y coordinates of the i-th point represented by the i-th elements of pointsX and pointsY, respectively. You play a game with your friend alternating turns. On your turn, you pick any white point and color it red. On his turn, your friend picks any white point and colors it blue. The game ends when there are no white points left, and the final score is the sum of all distances between pairs of points with different colors. Knowing that you make the first turn, and that your opponent plays optimally and wants to minimize the final score, return the highest final score you can achieve.

Definition

Class:
PointsGame
Method:
gameValue
Parameters:
int[], int[]
Returns:
double
Method signature:
double gameValue(int[] pointsX, int[] pointsY)
(be sure your method is public)

Notes

  • Your return must have relative or absolute error less than 1E-9.

Constraints

  • pointsX will contain between 2 and 12 elements, inclusive.
  • pointsY will contain the same number of elements as pointsX.
  • Each element of pointsX and pointsY will be between 0 and 1000, inclusive.
  • All points in the given set will be distinct.

Examples

  1. {0,0}

    {0,1}

    Returns: 1.0

    There are only 2 points and the answer is the distance between them.

  2. {0,0,1,1}

    {0,5,0,5}

    Returns: 12.198039027185569

    Your friend can always choose the closest point to get the smallest answer.

  3. {0,0,0,0}

    {0,1,5,6}

    Returns: 12.0

  4. {0,1,2,3}

    {0,0,0,0}

    Returns: 6.0

  5. {245,333}

    {245,333}

    Returns: 124.45079348883236

  6. {1,0,2}

    {1,2,0}

    Returns: 4.242640687119286

  7. {0,1000,1000,0}

    {0,0,1000,1000}

    Returns: 4828.42712474619

  8. {0,1000,1000,0,500}

    {0,0,1000,1000,500}

    Returns: 6242.640687119286

  9. {0,10,20,30,40,50}

    {331,331,331,331,331,331}

    Returns: 190.0

  10. {1,1,0,2}

    {0,4,1,1}

    Returns: 10.576491222541474

  11. {4,0,1,2}

    {3,3,1,0}

    Returns: 12.625316113301075

  12. {606,853,408,873}

    {249,224,577,629}

    Returns: 1748.5925527328632

  13. {501,502,503,504,505,506,507,508,509,510,0,1000}

    {365,365,365,365,365,365,365,365,365,365,365,365}

    Returns: 6080.0

  14. {100,100,50,150,0,200,100,100}

    {100,50,75,75,100,100,0,200}

    Returns: 1689.0841272698042

  15. {100,100,110,110,1000,900}

    {100,200,100,200,1000,700}

    Returns: 4943.0680876954

  16. {0,10,5,100,120,110,500,600,550,900,950,925}

    {10,13,41,100,100,101,333,334,390,784,800,999}

    Returns: 20178.992901151338

  17. {1,2,3,4,5,6,7,8,9,10,11,12}

    {1,1,2,2,3,3,4,4,5,5,6,6}

    Returns: 163.3864026599999

  18. {1,1000,5,995,10,990,15,985,20,980,25,975}

    {132,132,157,157,168,168,199,199,397,398,444,444}

    Returns: 20255.471525270357

  19. {0,1000,1000,0,100,900,900,100,400,600,600,400}

    {0,0,1000,1000,100,100,900,900,400,400,600,600}

    Returns: 24174.838387804008

  20. {41,449,328}

    {474,150,709}

    Returns: 942.8824539017646

  21. {467,329,936,440}

    {700,117,258,811}

    Returns: 2084.6757730933214

  22. {952,491,993,931,823}

    {431,359,590,899,153}

    Returns: 2702.7604748705803

  23. {292,370,404,698,699,876}

    {442,705,757,527,868,893}

    Returns: 3297.0560941390354

  24. {642,273,18,885,675,788,291}

    {303,656,660,126,704,225,862}

    Returns: 6166.298751483526

  25. {522,617,630,725,17,847,715,732}

    {502,778,304,32,168,841,288,76}

    Returns: 7616.440447170846

  26. {31,934,245,626,419,782,875,723,346}

    {335,992,70,369,545,610,611,60,935}

    Returns: 11540.18630439218

  27. {738,829,962,369,918,282,928,407,602,312}

    {532,517,102,80,907,525,829,84,635,629}

    Returns: 12320.440592540608

  28. {682,921,964,304,642,364,16,717,898,53,264}

    {824,751,558,92,496,963,277,152,618,333,743}

    Returns: 16690.543244691802

  29. {632,559,27,40,323,149,925,703,953,427,76,161}

    {990,326,442,275,726,373,931,901,177,749,197,570}

    Returns: 19735.83667467181

  30. {416,922,479}

    {17,397,139}

    Returns: 770.1063535206472

  31. {900,559,744,654}

    {393,353,597,517}

    Returns: 1028.0287837641897

  32. {527,477,568,37,599}

    {326,281,806,365,9}

    Returns: 2801.542455104784

  33. {592,998,321,176,649,460}

    {273,730,53,998,392,911}

    Returns: 5343.283940580763

  34. {894,785,109,467,725,879,624}

    {461,790,419,296,611,791,505}

    Returns: 4903.793736032305

  35. {295,609,917,434,580,244,503,525}

    {776,273,218,998,839,577,975,670}

    Returns: 6854.68843568223

  36. {192,465,90,329,493,586,285,494,441}

    {175,445,612,560,777,784,266,570,778}

    Returns: 6747.63274603254

  37. {982,130,452,599,520,280,32,155,172,628}

    {951,185,796,866,137,500,186,632,248,35}

    Returns: 13508.48465906824

  38. {308,624,336,882,857,405,840,122,821,415,860}

    {967,312,633,11,694,554,448,865,365,70,702}

    Returns: 15125.335760923686

  39. {598,508,983,843,844,674,388,780,240,407,998,575}

    {158,275,61,395,589,734,823,902,165,152,696,172}

    Returns: 17605.98616743397

  40. {957,298,366}

    {664,404,545}

    Returns: 864.9763299849204

  41. {431,533,434,503}

    {115,42,697,750}

    Returns: 1513.9452880833414

  42. {123,411,263,971,671}

    {517,527,420,847,937}

    Returns: 2933.9180340478006

  43. {193,172,294,396,258,89}

    {464,266,443,709,96,690}

    Returns: 2943.078649000805

  44. {285,651,781,251,309,331,154}

    {33,912,798,831,925,309,729}

    Returns: 6057.143141768428

  45. {293,539,623,955,481,140,173,202}

    {122,159,530,430,162,456,32,638}

    Returns: 6936.223323055949

  46. {266,413,236,4,128,481,741,629,173}

    {305,470,995,166,4,769,896,941,384}

    Returns: 10499.251613733048

  47. {192,622,451,410,305,799,305,849,348,139}

    {822,42,480,269,511,169,756,238,762,666}

    Returns: 10783.346910920187

  48. {175,972,99,472,184,620,798,95,497,623,542}

    {923,12,943,48,167,973,405,488,566,703,18}

    Returns: 18026.183322070705

  49. {484,142,205,255,51,893,168,352,391,944,256,141}

    {235,803,692,735,878,663,278,538,140,681,693,603}

    Returns: 15822.244539965537

  50. {123,550,673,636,276,354,444,674,571,828,459,17}

    {436,98,129,798,69,29,925,1,753,138,295,567}

    Returns: 18177.43218053535

  51. {31,736,157,104,875,69,536,484,548,460}

    {623,602,624,897,398,492,896,948,123,572}

    Returns: 12280.453031579706

  52. {248,185,493,263,252,196,108,25,306,983}

    {741,405,522,132,499,761,910,158,742,936}

    Returns: 11566.777335591754

  53. {644,816,870,696}

    {940,561,357,995}

    Returns: 1364.221044612128

  54. {199,32,433,301,748,338,322,471,103,92}

    {873,782,828,446,406,981,357,386,534,80}

    Returns: 11164.361918321192

  55. {823,324,66,321,805,471,536}

    {193,625,348,518,344,308,248}

    Returns: 4484.919721249233

  56. {332,884,9,588,102,705,678,574,17,399,105,205}

    {561,553,924,274,826,41,946,581,705,648,956,436}

    Returns: 18236.455991645213

  57. {510,961,605,481,911,624,57,826,671,926,221,120}

    {731,505,719,155,438,808,218,853,625,903,190,752}

    Returns: 18077.03766579361

  58. {381,257,679}

    {181,722,636}

    Returns: 985.7027186284172

  59. {551,992,166,680,956,538,866}

    {300,399,625,836,831,129,451}

    Returns: 6104.639590786683

  60. {847,404,646,751}

    {425,268,661,30}

    Returns: 1840.4461771698293

  61. {875,52,806,610,16,918}

    {84,665,156,808,20,462}

    Returns: 5991.098914162949

  62. {71,478,587,965,130,334,295,633}

    {714,22,247,335,751,181,598,239}

    Returns: 7740.360178579095

  63. {475,826,752,588}

    {263,992,532,527}

    Returns: 1726.257055119557

  64. {596,461,512,103}

    {209,786,145,581}

    Returns: 1778.771008822947

  65. {195,675,205,969,799,596,369,744,668,402}

    {1000,80,65,768,483,946,281,824,572,503}

    Returns: 13473.761595695109

  66. {641,701,361,1}

    {149,462,222,152}

    Returns: 1741.6214060383309

  67. {612,893,584,698,787}

    {223,750,180,971,538}

    Returns: 2538.2757084493983

  68. {411,77,236,571,635,969}

    {847,891,64,524,684,529}

    Returns: 5064.614165590969

  69. {768,247,511,972,261,929,863,522,222,483,290}

    {843,592,295,111,448,125,62,542,734,872,86}

    Returns: 15720.791749065389

  70. {409,524,589,943,1,560,28,522,322,86,941,625}

    {387,437,44,677,587,331,608,28,200,757,925,868}

    Returns: 19233.272491541447

  71. {132,690,942,831,409,595,748,40,532,763,17,194}

    {170,31,844,604,213,733,904,356,225,742,940,941}

    Returns: 21099.679348944475

  72. {295,694,386,4,335,971,527,487,566,506,947,319}

    {67,896,126,165,927,47,406,592,147,405,372,699}

    Returns: 18727.705040086264

  73. {606,783,356,63,549,20,722,112,784,989,248,646}

    {913,808,462,354,995,130,212,824,611,9,605,182}

    Returns: 20950.390516107174

  74. {671,649,657,613,883,343,395,439,995,255,211,449}

    {287,618,277,242,148,113,305,209,82,4,171,59}

    Returns: 12704.232977272048

  75. {297,842,26,131,330,249,892,673,614,883,888,558}

    {461,924,281,640,644,218,397,917,828,350,875,239}

    Returns: 18568.55022229078

  76. {990,597,948,974,924,772,478,380,653,288,692,584}

    {710,933,18,404,430,228,496,952,956,487,514,244}

    Returns: 17457.76106100607

  77. {913,841,58,686,958,238,102,199,531,808,312,36}

    {182,259,54,953,69,690,460,750,372,786,926,535}

    Returns: 21339.803994004393

  78. {97,678,93,873,50,788,954,114,927,661,87,999}

    {929,775,722,342,28,159,754,193,66,884,953,70}

    Returns: 24291.899264216485

  79. {322,845,127,281,136,805,667,614,622,596,306,689}

    {682,50,106,237,641,527,653,857,392,397,818,810}

    Returns: 16999.65914217648

  80. {509,699,638,58,654,945,339,681,15,651,707,58}

    {280,395,885,844,107,918,713,731,395,504,802,256}

    Returns: 18439.449079767386

  81. {309,597,876,283,458,11,115,604,90,783,80,533}

    {278,272,967,123,53,320,694,248,484,699,126,84}

    Returns: 17649.976334017643

  82. {423,951,698,675,989,51,244,472,220,397,891,856}

    {642,466,458,175,455,607,146,10,145,374,24,922}

    Returns: 18931.978471548733

  83. {637,429,596,777,94,803,263,586,271,779,334,428}

    {869,540,287,571,754,558,314,379,387,878,803,838}

    Returns: 14473.070358686307

  84. {790,206,445,909,658,229,496,930,531,132,137,654}

    {655,792,339,723,382,123,706,920,167,550,630,636}

    Returns: 17135.637118110375

  85. {60,491,510,475,600,508,221,558,905,455,538,934}

    {147,494,537,452,330,892,322,319,903,900,718,320}

    Returns: 15587.608819805508

  86. {319,277,381,629,684,136,560,930,116,503,324,995}

    {321,621,636,961,583,538,262,78,143,355,624,186}

    Returns: 16881.190844347428

  87. {867,803,368,565,243,626,145,801,943,579,940,269}

    {411,560,802,578,200,419,614,607,53,157,877,58}

    Returns: 17956.945008799896

  88. {496,270,676,564,574,148,141,951,331,5,242,407}

    {482,412,744,771,880,529,178,366,480,759,874,363}

    Returns: 15952.771786333622

  89. {888,227,456,474,966,795,96,522,556,780,580,165}

    {567,943,327,754,479,11,661,416,415,907,753,962}

    Returns: 17905.966960759157

  90. {1, 1000, 200, 200, 199, 561, 531, 891, 285, 631, 1000, 500 }

    {193, 199, 999, 1000, 1000, 300, 700, 100, 300, 99, 1000, 100 }

    Returns: 23237.38097477647

  91. {1, 2, 3, 298, 28, 287, 998, 765, 321, 402, 12, 801 }

    {0, 98, 201, 34, 29, 14, 4, 276, 876, 43, 15, 5 }

    Returns: 18167.81482529317

  92. {491, 517, 484, 450, 519, 474, 528, 508, 512, 514, 455 }

    {495, 531, 477, 511, 541, 545, 492, 477, 486, 541, 454 }

    Returns: 1536.8934428066705

  93. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

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

    Returns: 206.47518010647198

  94. {700, 321, 212, 532, 24, 15, 896, 347, 998, 109, 1000 }

    {1000, 170, 621, 222, 578, 124, 215, 396, 147, 962, 129 }

    Returns: 18647.539132306127

  95. {297, 141, 678, 542, 942, 742, 249, 685, 665, 609, 133, 532 }

    {392, 252, 746, 781, 96, 639, 446, 779, 894, 226, 685, 961 }

    Returns: 16901.04253835688

  96. {0, 90, 180, 270, 360, 450, 540, 630, 720, 810, 900, 990 }

    {0, 90, 180, 270, 360, 450, 540, 630, 720, 810, 900, 990 }

    Returns: 18582.766209582467

  97. {45, 543, 45, 321, 789, 453, 453, 321, 786, 45 }

    {456, 78, 421, 78, 56, 39, 71, 86, 72, 76 }

    Returns: 9119.905963834699

  98. {730, 237, 34, 8, 124, 688, 245, 343, 813, 952, 271, 282 }

    {299, 895, 443, 811, 57, 184, 679, 701, 573, 279, 550, 188 }

    Returns: 18877.109251631722

  99. {100, 23, 34, 43, 34, 121, 32, 324, 423, 432, 54, 32 }

    {123, 323, 234, 323, 21, 132, 12, 323, 13, 422, 213, 212 }

    Returns: 8855.099961559798

  100. {1, 2, 3, 4, 52, 23, 54, 30, 13, 98, 97, 90 }

    {1, 2, 3, 4, 52, 23, 54, 30, 13, 98, 97, 90 }

    Returns: 2104.3497808111656

  101. {0, 0, 0, 0, 0, 0, 0 }

    {1, 2, 3, 4, 5, 6, 7 }

    Returns: 30.0

  102. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

    {735, 392, 421, 532, 285, 275, 214, 255, 143, 725, 188, 549 }

    Returns: 7893.869578625478

  103. {220, 391, 707, 650, 957, 353, 182, 416, 635, 515, 580, 40 }

    {252, 168, 775, 621, 629, 536, 27, 72, 384, 40, 190, 8 }

    Returns: 16389.239227524744

  104. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 11 }

    {4, 5, 6, 7, 8, 9, 3, 2, 1, 44, 55, 77 }

    Returns: 886.7736053574109

  105. {0, 10, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 }

    {0, 10, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 }

    Returns: 19742.421330728408

  106. {383, 886, 777, 915, 793, 335, 386, 492, 649, 421, 362, 27 }

    {383, 886, 777, 915, 793, 335, 386, 492, 649, 421, 362, 27 }

    Returns: 14948.237354283618

  107. {772, 609, 362, 949, 728, 355, 91, 701, 717, 510, 76, 247 }

    {763, 132, 775, 938, 75, 79, 759, 72, 682, 840, 510, 362 }

    Returns: 19740.45574109664

  108. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

    Returns: 146.0

  109. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

    {10, 11, 12, 13, 141, 51, 16, 17, 18, 19, 20, 21 }

    Returns: 1048.7439301817876

  110. {0, 0, 1, 1, 121, 743, 12, 11, 11, 31, 21, 199 }

    {0, 5, 0, 5, 121, 743, 12, 11, 17, 888, 772, 661 }

    Returns: 15667.868320064328

  111. {400, 111, 999, 1000, 0, 200, 2, 999, 998, 876, 405, 888 }

    {1, 1000, 9, 940, 299, 1, 39, 994, 450, 239, 984, 583 }

    Returns: 26518.185249181905

  112. {23, 35, 123, 45, 123, 435, 56, 43, 34, 234, 567, 987 }

    {234, 456, 23, 12, 5, 7, 6, 5, 3, 2, 1, 34 }

    Returns: 12643.025604030572

  113. {33, 33, 741, 669, 217, 657, 594, 134, 298, 625, 864, 782 }

    {653, 59, 206, 238, 838, 220, 94, 507, 572, 180, 311, 513 }

    Returns: 17101.957420455423

  114. {258, 811, 952, 491, 993, 931, 823, 431, 359, 590, 899 }

    {41, 449, 328, 474, 150, 709, 467, 329, 936, 440, 700 }

    Returns: 13486.023548283956

  115. {1, 1000, 666, 472, 5, 0, 763, 224, 874, 953, 212 }

    {2, 46, 882, 762, 737, 848, 222, 319, 400, 555, 825 }

    Returns: 19412.97906948628

  116. {123, 581, 119, 304, 979, 128, 207, 335, 542, 877, 141, 923 }

    {224, 812, 203, 252, 841, 362, 203, 565, 769, 321, 500, 70 }

    Returns: 18356.869682204535

  117. {956, 506, 501, 602, 677, 200, 217, 150, 684, 988, 560, 472 }

    {243, 403, 450, 260, 60, 653, 578, 118, 0, 36, 405, 881 }

    Returns: 16883.754020084038

  118. {0, 123, 123, 234, 234, 45, 564, 234, 164, 543, 234, 987 }

    {892, 100, 200, 300, 987, 154, 543, 678, 456, 876, 447, 157 }

    Returns: 18502.943579703115

  119. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

    Returns: 206.47518010647198

  120. {10, 20, 30 }

    {10, 20, 30 }

    Returns: 42.42640687119285

  121. {0, 0, 1000, 1000, 500, 500, 1000, 0, 500, 1, 998, 3 }

    {0, 1000, 1000, 0, 0, 1000, 500, 500, 500, 1, 999, 3 }

    Returns: 28583.066436488036

  122. {111, 222, 333, 444, 555, 666, 777, 888, 999, 123, 456, 789 }

    {654, 678, 423, 345, 932, 234, 123, 765, 245, 876, 132, 111 }

    Returns: 19101.643636538745

  123. {100, 50, 150, 300, 400, 500, 600, 700, 12, 34, 45, 584 }

    {12, 4, 856, 56, 743, 356, 94, 344, 353, 90, 56, 34 }

    Returns: 16904.383571851162

  124. {473, 765, 275, 374, 987, 457, 347, 715, 852, 654, 887, 567 }

    {999, 1, 43, 887, 478, 976, 439, 100, 1000, 356, 994, 275 }

    Returns: 20553.461834757225

  125. {385, 772, 381, 755, 474, 175, 471, 954, 241 }

    {161, 519, 101, 852, 326, 259, 733, 443, 343 }

    Returns: 8947.146686004551

  126. {0, 30, 12, 503, 123, 999, 405, 0, 832, 213, 92, 12 }

    {983, 12, 0, 234, 745, 23, 12, 853, 999, 123, 0, 532 }

    Returns: 23801.68326725385

  127. {1000, 666, 472, 5, 0, 763, 224, 874, 953, 212 }

    {46, 882, 762, 737, 848, 222, 319, 400, 555, 825 }

    Returns: 14956.378122045786

  128. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

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

    Returns: 146.0

  129. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

    Returns: 206.47518010647198

  130. {0, 516, 660, 350, 716, 614, 694, 459, 708, 92, 398, 985 }

    {582, 58, 414, 400, 463, 281, 402, 505, 152, 362, 798, 345 }

    Returns: 15113.500931159651

  131. {1, 2, 234, 234, 777, 222, 33, 44, 878, 234, 222, 35 }

    {57, 234, 86, 2, 565, 345, 945, 234, 99, 22, 44, 942 }

    Returns: 18525.727730376708

  132. {0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3 }

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

    Returns: 67.06781710355924

  133. {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8 }

    {9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 7, 4 }

    Returns: 162.70084998863524

  134. {0, 0, 0 }

    {1, 2, 3 }

    Returns: 3.0

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: