[BOJ] 백준 1007번: 벡터 매칭

https://www.acmicpc.net/problem/1007

1007번: 벡터 매칭

N개의 좌표점이 주어지고 (N은 짝수) N/2개의 벡터를 만들 때, 모든 벡터의 합이 최소가 되는 크기를 구하는 문제입니다.

20개의 벡터 쌍을 구하는 경우의 수는 20C2 + 18C2 +...+ 4C2 + 2C2 이므로 20! / 2^10 으로 다른 방법을 찾아봐야겠습니다. 2,432,902,008,176,640,000 / 1024 = 2,375,880,867,360,000

벡터의 합과 차

위의 벡터의 합과 차에 대한 개념으로 임의의 4개의 좌표점으로 구성된 두 벡터쌍의 합은 아래와 같습니다.

모든 벡터의 시작점을 원점으로 두는것과 같아집니다. 즉 시작점이 같으므로 두 집단의 차이 역시 좌표값의 차이로 나타낼 수 있죠.

즉, N/2개의 좌표점을 더하는 집단과 (b와 d같은) 빼는 집단 (c와 a같은) 두가지로 나누는 경우의 수는 20개 중에서 10개를 선택하는 방법이므로 20C10 = 184,756로 충분히 빠르게 수행가능합니다.

 

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef double d;
typedef pair<d, d> pdd;
typedef pair<int,int> pii;
int n;
int half;
pdd p[21];
int visit[21];
d cal() {
	pdd pos = { 0,0 };
	pdd neg = { 0,0 };
	for (int i = 0; i < n; i++) {
		if (visit[i]) {
			pos.first += p[i].first;
			pos.second += p[i].second;
		}
		else {
			neg.first += p[i].first;
			neg.second += p[i].second;
		}
	}
	d _dist = sqrt((pos.first - neg.first) * (pos.first - neg.first) + (pos.second - neg.second) * (pos.second - neg.second));
	return _dist;
}
d dfs(int index, int level) {

	if (level == half) { //
		return cal();
	}
	d _min = 40000000007.0;
	for (int i = index; i < n; i++) {
		visit[i] = 1;
		_min = min(_min,dfs(i + 1, level + 1));
		visit[i] = 0;
	}
	return _min;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	cout << fixed;
	cout.precision(7);
	for (; t--;) {
		memset(visit, 0, sizeof(visit));
		cin >> n;
		half = n / 2;
		for (int i = 0; i < n; i++) {
			cin >> p[i].first >> p[i].second;
		}
		cout << dfs(0, 0)<< "\n";
	}
}