Connection Status:
Competition Arena > VectorMatching

VectorMatching

TCCC07 Qual 3 · 2007-07-30 · by ivan_metelsky

TCCC07 Qual 3 · 2007-07-30 · by ivan_metelsky · Brute Force, Geometry
Class Name: VectorMatching
Return Type: double
Method Name: minimumLength
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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
0)
{-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.

1)
{-100000, 100000}
{-100000, 100000}
Returns: 282842.71247461904
2)
{26, 65, 78, 92, -60, -27, 42, -86, 92, -41}
{-76, -83, 38, 22, -42, 85, 46, 98, -47, 38}
Returns: 13.341664064126334
3)
{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
4)
{-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

Submissions are judged against all 46 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class VectorMatching with a public method double minimumLength(vector<int> x, vector<int> y) · 46 test cases · 2 s / 256 MB per case

Submitting as anonymous