[백준 1007] 벡터 매칭 (C++)

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

1007번: 벡터 매칭

1. 주의할 점

- 소수점 12자리 출력

- cout << fixed;
cout.precision(12);
cout << ans;

로 제출했을 때에는 틀리게 나오고, printf("%.12lf\n", ans); 로 제출하면 맞게 나온다. 이유는 정확히 모르겠고, 소수점 계산하면서 뭔가 잘못되는것 같다

 

2. 구현

- 두 점 사이의 벡터는 한쪽에서 한쪽을 빼줘야 한다. 즉, 한쪽은 그대로, 한쪽은 -를 붙인값을 더한다 -> N/2개는 그대로, N/2는 -부호를 붙이고 더한다

- Next_permutation()을 통해 nCn/2의 경우의 수를 모두 수행하면서 Result와 비교하여 기존 Result보다 작으면 갱신한다

- 마지막에 Sqrt(Result)를 Ans에 저장하고 소수점 12째자리까지 출력한다(6개까지만 해도 상관없다)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <math.h>
using namespace std;
int x[20], y[20];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int test, num;
	long long result;
	double ans;
	cin >> test;
	for (int t = 0; t < test; t++) {
		cin >> num;
		result = 9223372036854775807;
		for (int i = 0; i < num; i++) {
			cin >> x[i] >> y[i];
		}
		vector<int> v;
		for (int i = 0; i < num / 2; i++)
			v.push_back(0);
		for (int i = 0; i < num / 2; i++)
			v.push_back(1);
		do {
			long long tx = 0, ty = 0;
			long long t_result;
			for (int i = 0; i < num; i++) {
				if (v[i] == 0) {
					tx += x[i];
					ty += y[i];
				}
				else {
					tx -= x[i];
					ty -= y[i];
				}
			}
			t_result = tx * tx + ty * ty;			
			result = min(result, t_result);
	
		} while (next_permutation(v.begin(), v.end()));
		ans = sqrt(result);
		printf("%.12lf\n", ans);
	}
	system("pause");
	return 0;
}