[BOJ] 백준 1007 벡터 매칭

문제 링크

www.acmicpc.net/problem/1007

1007번: 벡터 매칭

 

풀이

나이브하게 가능한 모든 벡터를 구한다고 생각해봅시다.

점을 두 개씩 짝지어 $\frac{N}{2}$개의 벡터를 만들고, 각 벡터마다 두 개의 방향이 존재합니다.

이는 $O(N*(N-2)*(N-4)*...*2*2)$정도 됩니다. 당연히 안 되겠죠.

 

조금 더 생각을 해봅시다.

어떤 두 점 $(x_1, y_1)$, $(x_2, y_2)$로 벡터를 만들면 $(x_1-x_2,\ y_1-y_2)$ 혹은 $(x_2-x_1,\ y_2-y_1)$입니다. 벡터를 이루는 점 중 항상 한 점은 더해주고, 한 점은 빼주는 것을 알 수 있습니다.

 

즉, 더해줄 점 $\frac{N}{2}$개만 결정해주면 나머지 점의 좌표는 빼주기만 하면 됩니다. 복잡도는 $O((\frac{N}{2})!)$이므로 충분히 시간 안에 가능합니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

int n;
pii p[22];

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

    int t;
    cin >> t;
    cout.precision(7);
    cout << fixed;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> p[i].ft >> p[i].sd;
        }
        vi subset(n / 2, 0), tmp(n / 2, 1);
        subset.insert(subset.end(), all(tmp));
        ll ans = INF;
        do {
            ll x = 0, y = 0;
            for (int i = 0; i < n; i++) {
                if (subset[i]) x += p[i].ft, y += p[i].sd;
                else x -= p[i].ft, y -= p[i].sd;
            }
            ans = min(ans, x * x + y * y);
        } while (next_permutation(all(subset)));
        cout << sqrt(ans) << '\n';
    }
}