Statistics

Problem Statement for "VectorMatching"

Problem Statement

Let P be a set of an even number of distinct points on the plane. A vector matching V of set P is a set of vectors where each vector starts at one point in P and ends at another, and each point in P is either the head or tail of exactly one vector in the matching. Thus, there are half as many vectors in V as there are points in P.

You are given int[]s x and y, where (x[i], y[i]) are the coordinates of the i-th point of P. Find a vector matching V for set P such that the length of the vector sum of the vectors in V is minimal, and return this length.

Definition

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

Notes

  • The sum of two vectors (x1, y1) and (x2, y2) is the vector (x1 + x2, y1 + y2).
  • A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

  • x will contain between 2 and 20 elements, inclusive.
  • y will contain the same number of elements as x.
  • The number of elements in x will be even.
  • Each element of x and y will be between -100000 and 100000, inclusive.
  • All points will be distinct.

Examples

  1. {-5, -5, 5, 5}

    {-5, 5, 5, -5}

    Returns: 0.0

    The optimal matching consists of vectors (-5, -5) -> (-5, 5) and (5, 5) -> (5, -5). It contains two opposite vectors, so their vector sum is the zero vector.

  2. {-100000, 100000}

    {-100000, 100000}

    Returns: 282842.71247461904

  3. {26, 65, 78, 92, -60, -27, 42, -86, 92, -41}

    {-76, -83, 38, 22, -42, 85, 46, 98, -47, 38}

    Returns: 13.341664064126334

  4. {92383, 42478, 26103, -51063, 72172, -17487, 22179, 80130, 38797, -38546, 24521, -47024, -71456, -20740, 63751, -96441, 71347, 34233, 49104, 58014}

    {-18240, -56841, 57506, -22762, -65260, -42804, -34950, 27245, -41611, -69322, 38655, -26671, 54570, 12287, 31971, 15145, 4057, 70458, 56643, -24482}

    Returns: 473.68871635283864

  5. {-18240, -56841, 57506, -22762, -65260, -42804, -34950, 27245, -41611, -69322, 38655, -26671, 54570, 12287, 31971, 15145, 4057, 70458, 56643, -24482}

    {89861, -33037, -43522, 91944, -83433, -88019, 51084, 74300, 16394, -36766, -94707, 96329, 9616, 50182, 32869, 40898, 10293, 54808, -38266, 96754}

    Returns: 814.164602522119

  6. {-79, -95, 36, -80, -22, -64, -37, -88}

    {48, 46, -26, -13, -58, -17, 9, 0}

    Returns: 18.384776310850235

  7. {-90, 73, 85, -74, 50, -25, 27, 86, -12, 34, 15, 13, 65, -23, -15, 7}

    {-55, 27, -62, 15, -21, 72, 72, -12, -28, 81, 71, 93, 91, -7, -70, -46}

    Returns: 5.0

  8. {-5, 7, -5, -8, 9, 7, 4, -5, 5, -6, -10, 3}

    {-5, 9, 3, -7, 10, -9, 1, 6, 7, -8, 8, 6}

    Returns: 1.0

  9. {9240, 4255, -2355, 9827, -9148, -5823}

    {7833, -5212, 9506, -5566, 5797, 2434}

    Returns: 3384.8397303269767

  10. {56150, -86032, -25267, -89273, -33231, 64697, 33922, -33070, 14974, 22368, 29000, 87924, -17563, 36041}

    {91908, -93247, 81856, 78959, 69047, -68306, -73621, 9250, 83458, 24660, 62275, 31825, 92638, 42513}

    Returns: 1678.1004141588191

  11. {-7, -9, -4, 0, -1, -4, -9, 6, -2, -7, 10, 7, 2, -1, 4, 3, 2, 7, -9, 0}

    {9, -3, 7, 3, 1, -8, 8, -2, 0, -7, -10, 4, -2, -9, 0, -3, 9, 10, -4, -3}

    Returns: 0.0

  12. {12, 10, -96, -92, 37, -47, 19, 72}

    {56, -66, 85, 64, 82, 55, -22, 50}

    Returns: 14.866068747318506

  13. {2993, -33463, 41155, 60955, 98588, -59937, -32194, -40487, 4137, 87953, -78077, 32783}

    {68178, -28799, -66420, 30975, -10518, 58859, -46836, 38926, 83717, -51269, 312, 45101}

    Returns: 6432.615020347479

  14. {-80, -939, -568, 682, -484, 477, -723, 717}

    {243, 908, -98, -547, 310, -469, 358, -246}

    Returns: 97.082439194738

  15. {-85, -44, -83, 44, -15, -82}

    {-27, 66, -74, -97, 12, -25}

    Returns: 99.32774033471213

  16. {-59002, -2493, 76501, 85961}

    {-16458, -19157, -71243, 55179}

    Returns: 137425.76556817867

  17. {-543, -489, 756, -790, -360, 737, 392, -23, -550, 535, -97, 838}

    {-534, -5, 17, -836, -180, 636, -554, 893, 861, -396, 910, 924}

    Returns: 132.43866504914644

  18. {1957, 7014, 1504, 1486, -2518, 5823, -5625, 9304, -8284, -1789}

    {-9255, 6607, -9023, 7287, -1680, 7846, -453, -681, 1619, -8647}

    Returns: 1636.0256721702137

  19. {1, -6, 6, 4}

    {3, 5, 2, -3}

    Returns: 8.602325267042627

  20. {7898, 3032, -6367, 7539, 3725, -5437, 252, 8326, -720, 7929, 8538, -8427, -3197, 7371, -9091, 8261}

    {-1949, 9904, 8337, -3503, 7878, 9061, 1878, -39, -3168, 2248, -9863, 5359, 9474, -9830, -1285, -8454}

    Returns: 117.2006825918689

  21. {6, 3, 1, -2, 6, -2}

    {-7, 9, 5, 10, 8, -9}

    Returns: 2.0

  22. {731, 177, -769, 853, 168, -371, -760, -623, 986, -805, -494, -339, 220, 689}

    {253, 726, 434, 192, -982, -315, -742, -308, -156, 942, -508, 885, -715, -458}

    Returns: 85.16454661418682

  23. {9, -5, -2, 5, 7, 9, 3, -10, -9, -4, -3, 0, 0, -10, -8, 6, -1, -8, -2, -1}

    {1, -9, -3, -2, 9, -3, -9, 3, 1, 10, -5, -2, -8, -3, -10, -9, -1, -3, -2, 4}

    Returns: 1.0

  24. {-5, 3, -2, 1, 9, 1, -9, -1, 9, -6, 2, 5, 3, -7, 6, -3, -7, 7, 1, -5}

    {-2, 10, -7, 8, -4, 4, 8, 5, 5, -6, -7, 8, 3, 1, -4, 8, 3, -6, -5, -7}

    Returns: 1.0

  25. {-806, -142, -459, -718, -115, 625, 531, -566, -694, -134, -774, 362, -96, -828}

    {-333, 581, -246, -665, 920, 228, -423, -80, -735, 989, 845, -266, 928, 396}

    Returns: 116.24543001770004

  26. {-15939, -55712, 78828, 91332, 93716, -21477, -40401, 81683, 81665, 78217, -8097, 65937, 86184, -8283, 84199, -36048, 8330, -87490, 52747, -36676}

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

    Returns: 1.0

  27. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    {-13453, 91886, -58970, -37829, -3677, -4830, 15863, -68390, -74756, 32117, -34971, -65174, -39088, -71139, 41638, 73170, -13267, 41977, -70402, -5024}

    Returns: 3.0

  28. {-53512, -61847, -44697, -10780, -58742, -22785, 22916, 8310, 46909, 49922, 88047, 43894, -19900, -73023, 93025, 1369, -65373, -54132, -9707, -20863}

    {-53512, -61847, -44697, -10780, -58742, -22785, 22916, 8310, 46909, 49922, 88047, 43894, -19900, -73023, 93025, 1369, -65373, -54132, -9707, -20863}

    Returns: 7.0710678118654755

  29. {-58486, -8857, 96700, 2758, 43211, -57848, 46962, -17183, -51224, -36875, -80892, -22223, -61441, -24459, 63883, -96813, 46314, -15696, -96500, 48107}

    {-89896, -25039, -65200, 35087, 26866, -26040, -43546, 15019, 34228, -97883, 56084, -44014, -93969, 36511, 81310, 46634, 32869, -22506, -76581, 80952}

    Returns: 1186.3102460992234

  30. {66485, 96712, 33582, -25249, -56885, 38977, -14634, -43635, 77550, 16952, 42982, 537, -45775, -81003, -83476, 6308, 52818, 59873, -20782, -40955}

    {48524, -84862, -29904, -14652, 13387, -99292, 35961, -46682, 49838, 44230, -88053, -59258, -33285, 54797, -13139, 60282, -79507, -25322, -529, -16346}

    Returns: 1062.5798793502538

  31. {99751, -94994, 94604, -94490, -94364, 90721, 95501, -96509, -98521, -94542, -98986, 94910, -94110, -94414, -95139, 96144, -96146, 99288, -97912, -96475}

    {97962, -94354, 98386, -94921, -97309, 94417, 94853, -91858, -93010, -96969, -90531, 92448, -99266, -96053, -93772, 95557, -94583, 91646, -91392, -90486}

    Returns: 244883.3398375643

  32. {66448, 47832}

    {-16167, -97922}

    Returns: 83847.69216263498

  33. {-67153, 61638, 83156, -81338, 87664, -86743}

    {-87731, -95397, 98143, -75073, -97163, -70512}

    Returns: 223319.26816331813

  34. {-95282, 97291, -98409, -95847}

    {-84122, -84461, -85273, 95923}

    Returns: 262791.05073422875

  35. {55981, -68125, 67319, -78778, -71530, -53384, -43069, 83415}

    {93364, -94513, -84230, 95153, -94863, -92768, -99107, 97610}

    Returns: 196220.38482532848

  36. {32953, 55397, 76891, -88364, 76152, 38963, -51364, 85859, 3203, -27270}

    {96146, 88365, 97734, -78542, -98868, 98203, -78518, 89194, -78894, -82127}

    Returns: 160340.22186899954

  37. {100,200,300,100,200,300}

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

    Returns: 1.0

  38. {26, 65, 78, 92, -60, -27, 42, -86, 92, -41 }

    {-76, -83, 38, 22, -42, 85, 46, 98, -47, 38 }

    Returns: 13.341664064126334

  39. {-85252, -87668, -19267, 92352, -86910, -12168, -15691, 41732, -54902, -37578, -61776, -16200, 38665, 47136, -48240, 68892, 96494, 58437, -52865, 63202 }

    {51389, -77605, 7364, 28239, 29661, -7405, -27597, 30777, -29144, -41364, -52432, -3914, 86539, -20446, -28378, -88578, -56705, 43463, -46145, -35348 }

    Returns: 704.7056122949497

  40. {26, 65, 78, 92, -60, -27, 42, -86, 92, -41, 1, 2, 3, 4 }

    {-76, -83, 38, 22, -42, 85, 46, 98, -47, 38, 1, 5, -56, 34 }

    Returns: 3.1622776601683795

  41. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

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

    Returns: 0.0

  42. {443, 4235, 42, 6, 2235, 52, 5465, 9999, 9998, -2346, -26, -4235, -426, -4236, 235, 4235, 4236, 423, 654, 32 }

    {23, 67, 468, 34, -2, -5, -65, -87, -897, -9998, -2, -54, 54, 7, 9999, 684, 2346, 6589, 9989, 5476 }

    Returns: 52.46903848937962

  43. {-1074, 9344, -3397, -7275 }

    {9729, -6885, 5695, 4048 }

    Returns: 19396.79666852236

  44. {-20000, 30000 }

    {50000, 70000 }

    Returns: 53851.648071345044

  45. {0, 1, 5, -4 }

    {0, 0, 0, 0 }

    Returns: 0.0

  46. {41, 467, 334, 500, 169, 724, 478, 358, 962, 464, 705, 145, 281, 827, 961, 491, 995, 942, 827, 436 }

    {391, 604, 902, 153, 292, 382, 421, 716, 718, 895, 447, 726, 771, 538, 869, 912, 667, 299, 35, 894 }

    Returns: 3.605551275463989

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: