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

www.acmicpc.net/problem/1007

1007번: 벡터 매칭

벡터의 합에는 더해지는 부분과 빼지는 부분이 있으므로 더해지는 점을 골라서 (골라지지 않은 점은 빼지는 점) 벡터 합의 길이를 구해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int tc;
int n;
vector<pair<int, int>> p;

void Pre()
{
	p.clear();
}

//더해지는 점을 절반 고른다
double Solve(vector<int>& selected_check, int selected_num, int last_selected)
{
	//더하는 점 절반을 골랐을때 (골라지지 않은 점은 빼지는 점)
	if (selected_num == n / 2)
	{
		long long plus_sum_x = 0;
		long long plus_sum_y = 0;
		long long minus_num_x = 0;
		long long minus_num_y = 0;

		for (int i = 0; i < selected_check.size(); i++)
		{
			if (selected_check[i] == 1) //더해지는 점일때
			{
				plus_sum_x += p[i].first;
				plus_sum_y += p[i].second;
			}

			else //빼지는 점일때
			{
				minus_num_x += p[i].first;
				minus_num_y += p[i].second;
			}
		}

		//백터합의 길이를 구한다
		return sqrt(pow(plus_sum_x - minus_num_x, 2) + pow(plus_sum_y - minus_num_y, 2));
	}

	double ret = numeric_limits<double>::max();
	for (int i = last_selected + 1; i < n; i++)
	{
		selected_check[i] = 1;
		ret = min(ret, Solve(selected_check, selected_num + 1, i));
		selected_check[i] = 0;
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n;

		for (int i = 0; i < n; i++)
		{
			int x, y;
			cin >> x >> y;

			p.push_back(make_pair(x, y));
		}

		vector<int> selected_check(n, 0);

		cout << fixed;
		cout.precision(6);

		cout << Solve(selected_check, 0, -1) << "\n";
	}

	return 0;
}