BOJ #1007 Vector Matching(Mathematics)

This is a Gold II problem. At first, I thought that it was a TSP program using dynamic programming, and I worked hard. It was a Gold I problem when I solved the problem, but the difficulty rating has been reduced.

Somehow vector matching is the problem name, but it wasn't a TSP problem. And if it was a TSP problem, it would have been given a more difficult rating. If it was a TSP problem, you would have to answer it with dynamic programming using bitmasking. I've done all that annoying programming. The maximum number of points is 20, so even if it was a TSP problem, it would have been solved in time.

 

 

The problem is; Given N points in two-dimensional space, each two of these points can be paired and be made a vector. N points are paired and made N/2 vectors.  The objective here is to make the sum of the vectors is minimal and display the vector's length.

 

What's important in this problem is that half of the points add up and the other half subtract to give the smallest length.

The most ignorant way to do it is to choose half as you travel. The maximum number of points is 20, so if you select 10 out of 20, the number is not too large.

 

\[ \binom{20}{10} = 184,756 \]

 

If the number is in units of tens of thousands, the number of cases in which the test case comes in time, unless it is several thousand units. Received 48ms when receiving AC Many people have achieved better results.

The problem is that if you do \(V_i + V_j\), you add up the magnitude of each vector. So we add 10 points out of 20 and subtract 10 points to get the length of the final vector.

 

//----------------------------------------------------------
//  baekjoon #1007 - Vector Matching
//    - by Aubrey Choi
//    - created at 2019-12-29
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>

int n, x[20], y[20];
double getOpt(int c, int p, int m, int xs, int ys)
{
  if(c==n) return sqrt((double)xs*xs+(double)ys*ys);
  double min=1e10, r;
  if(p<n/2) { r=getOpt(c+1, p+1, m, xs+x[c], ys+y[c]); min=(r<min)?r:min; }
  if(m<n/2) { r=getOpt(c+1, p, m+1, xs-x[c], ys-y[c]); min=(r<min)?r:min; }
  return min;
}
int main()
{
  int t, i, j;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d%d",x+i,y+i);
    printf("%.8lf\n", getOpt(0, 0, 0, 0, 0));
  }
}