[BOJ/백준][Gold2] 1007 : 벡터 매칭 (C++)

www.acmicpc.net/problem/1007

1007번: 벡터 매칭

 

 

[난이도] Gold2

[유형] 완전탐색

 

[풀이]

N이 20이기 때문에 임의로 N/2, N/2 그룹으로 나누어서 푼다

20C10의 경우의 수 중에 최솟값을 찾으면 된다.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,x[20],y[20];
long long xsum[2],ysum[2];
double ans;
bool a[20];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d%d",&x[i],&y[i]);
        memset(a,0,sizeof(a));
        for(int i=N/2;i<N;i++) a[i]=1;
        
        ans = -1;
        do{
            ysum[0]=ysum[1]=xsum[0]=xsum[1]=0;
            for(int i=0;i<N;i++) {
                xsum[a[i]]+=x[i];
                ysum[a[i]]+=y[i];
            }
            double tmp = sqrt((xsum[0]-xsum[1])*(xsum[0]-xsum[1])+(ysum[0]-ysum[1])*(ysum[0]-ysum[1]));
            if(ans < 0 || ans > tmp) ans = tmp;
        }while(next_permutation(a,a+N));
        printf("%f\n",ans);
    }
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1007.cpp