[백준][C++] 1007: 벡터 매칭

문제 링크: https://www.acmicpc.net/problem/1007

 

문제가 조금 복잡한데요 풀이는 그렇게 어렵지 않은 문제입니다.

일단 입력으로 평면상의 점의 좌표가 주어집니다. 벡터 크기만 쓸거니까 (x, y), 아니면 (y, x) 뭐든 상관 없습니다.

그 다음, 이 점들을 모두 사용해서 벡터를 만든 뒤 벡터의 합의 길이 중 최소값을 구하는 것이 문제입니다. 벡터의 합은 x좌표는 x좌표끼리, y좌표는 y좌표끼리 더한 것이 됩니다.

 

점의 개수가 20개 이하이기 때문에 브루트포스로 모든 조합을 만들어보면 됩니다.

점을 절반씩, 한쪽은 from, 한쪽은 to로 나눕니다. 그 다음 ((from의 x좌표 합 - to의 x좌표 합), (from의 y좌표 합 - to의 y좌표 합)) 이 벡터의 크기를 구하면 됩니다.

절반씩 나눌 때 브루트포스로 조합을 만들어보면 되겠죠. 벡터의 크기는 원점에서 (x, y)까지의 거리를 구하면 됩니다

 

처음에 문제를 대충 읽었을 때 입력으로 벡터가 주어지고 두 벡터의 합이 최소가 되는 경우를 출력하는 줄 알고 O(N^2) 알고리즘으로 후다닥 풀어봤는데 역시나 아니었습니다. 문제를 좀 잘 읽어봐야겠습니다.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;

constexpr double sq(double a) { return a * a; }

// 벡터의 크기
// (0, 0) -> (x, y)
inline double dst(int x, int y) {
	return sqrt(sq(y) + sq(x));
}


vector<pair<int, int>> vp;	// x, y
ll x_sum, y_sum;
double min_sum;

void bruteforce(int n, vector<int>& picked, int toPick) {
	if (toPick == 0) {
		ll partial_x = 0, partial_y = 0;
		for (auto& c : picked) {
			partial_x += vp[c].first;
			partial_y += vp[c].second;
		}

		ll diff_x = partial_x - (x_sum - partial_x),
			diff_y = partial_y - (y_sum - partial_y);

		min_sum = min(min_sum, dst(diff_x, diff_y));

		return;
	}

	int smallest = picked.empty() ? 0 : picked.back();	// 오름차순
	for (int i = smallest + 1; i < n; ++i) {
		picked.push_back(i);
		bruteforce(n, picked, toPick - 1);
		picked.pop_back();
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;

		x_sum = 0, y_sum = 0;
		min_sum = 1e9;

		vp.resize(n);
		for (auto it=vp.begin(); it!=vp.end(); ++it) {
			cin >> it->first >> it->second;
			x_sum += it->first;
			y_sum += it->second;
		}

		vector<int> picked;
		bruteforce(n, picked, n / 2);

		cout << setprecision(7) << fixed << min_sum << '\n';
	}

	return 0;
}