백준 1007, 벡터 매칭

문제

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

풀이

처음에는 어? 점, 어 다있는 건가? 어 트리? 해가지고 크루스칼 적용해서 풀었는데 다시보니까 점은 짝수고... 벡터는 절반이고... 그때부터 멘탈 나가서 다시봐도 기억안나서 밑에 분류보니까 완탐이길래

1차 현타오고... 그걸로 계산기 두두려봐도 시간이 너무 오래 걸리길래 결국 블로그 들어가서 좌표로 두개 나누는 것만 보니까 바로 풀이 떠오름...

전체는 안봤지만 아마 빼는 쪽, 더하는쪽으로 반으로 나눠서 풀었을 것이라 추측함. (이거밖에 없지 않을까 생각)

그렇게 하면 nCp개로 처리가능하기 때문에 최대 18만으로 구현 가능..

실수

• 초기화를 이상한데서 해서 시간 10분 걸림
• 항상 완전탐색부터 시작하자. 아니면 잘 생각안나면 완탐으로 시도해보자.
• next permutation은 index 0 쪽에는 0을 뒤에는 1을 채워야 잘 돌아간다 (00001111 앞이 인덱스가 빠른순)

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<pair<int, int>> dot(30, make_pair(0, 0));
vector<int> CB(30, 0);

int main() {

	int t;

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {

		int n;

		double a, b;

		double sum = 2e13;

		scanf("%d", &n);

		for (int j = 0; j < n; j++) {

			scanf("%d %d", &dot[j].first, &dot[j].second);

		}

		for (int j = 0; j < n; j++) {

			if (j < n / 2)
				CB[j] = 0;

			else
				CB[j] = 1;

		}
		
		do {

			a = 0;
			b = 0;

			for (int j = 0; j < n; j++) {

				if (CB[j] == 0) {

					a += dot[j].first;
					b += dot[j].second;

				}

				else {

					a -= dot[j].first;
					b -= dot[j].second;

				}

			}

			sum = min(sum, sqrt(a * a + b * b));


		} while (next_permutation(CB.begin(), CB.begin() + n));

		printf("%lf\n", sum);

	}

	return 0;

}