TopCoder VectorMatching

https://community.topcoder.com/stat?c=problem_statement&pm=8023&rd=10889

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 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 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)2010, TopCoder, Inc. All rights reserved.

https://apps.topcoder.com/forums/?module=Thread&threadID=671150&start=0

In this problem we are given n points and we are asked to find a vector matching that has the minimal length. The number of points is small (n=20) which allows us to iterate over all possible vector matchings. A vector matching consists of two sets of points A and B, such that the head of the i-th vector is the i-th point in A and its tail is the i-th point in B. A and B should have the same number of elements, namely n/2. Each point can be either in set A or in set B, so we have 2^n possible states. However, we only need to consider those states where the size of A is n/2. This reduces the problem to Choose(20,10) = 185756 states.

Suppose the point (x1,y1) is in A and the point (x2,y2) is in B. The vector represented by these two points is (x2-x1,y2-y1). Hence if a point is in A then it contributes negatively to the vector sum; otherwise it is in B and it contributes positively. So now we can determine the vector sum (which is a vector) as we iterate through the points in A and B; its x-component will be sumX and its y-component will be sumY:

minimumLength(int[] x, int[] y)
  {
    double result = Double.MAX_VALUE;
    int n = x.length;
    for (int i = 0; i < (1 << n); i++)
    {
      //size of A and B must be n/2
      if (2*Integer.bitCount(i) != n) continue;  
 
      long sumX = 0;
      long sumY = 0;
      for (int k = 0; k < n; k++)
      {
 //point (x[k],y[k]) is in B
 if ((i&(1<<k)) > 0)
 {
          sumX += x[k];
          sumY += y[k];
        }
 //point (x[k],y[k]) is in A
 else
 {
          sumX -= x[k];
          sumY -= y[k];
        }
      }
 
      double length=Math.sqrt(sumX*sumX + sumY*sumY);  //vector length
      result = Math.min(result,length);  //record the minimum length
    }
    return result;
  }

https://github.com/ibudiselic/contest-problem-solutions/blob/master/tc%20tournaments/VectorMatching.cpp