백준[1007] 벡터 매칭

벡터 매칭

문제 링크

http://icpc.me/1007

1007번: 벡터 매칭

풀이

수학 문제다.

(a, b), (c, d) 점이 있을 때, (a-c, b-d) 또는 (c-a, d-b)인 두 벡터로 만들 수 있다.

위와 같은 성질을 이용하면 모든 점들 중 반절을 -를 곱하여 모두 더한 후 길이의 최솟값을 구하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

bool positive[22];
vector<pll> v;
ll ans = 1e12;
int n; 

ll calc() {
    ll a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (positive[i]) {
            a += v[i].first;
            b += v[i].second;
        } else {
            a -= v[i].first;
            b -= v[i].second;
        }
    }
    return a * a + b * b;
}

void solve(int cur, int p) {
    if (cur == n) {
        if (p == n / 2) ans = min(ans, calc());
        return;
    }
    positive[cur] = true;
    solve(cur + 1, p + 1);
    positive[cur] = false;
    solve(cur + 1, p);
}

int main() {
    int t; cin >> t;
    while (t--) {
        memset(positive, false, sizeof(positive));
        v.clear();
        ans = 1e12;
        cin >> n;
        for (int i = 0; i < n; i++) {
            int a, b; cin >> a >> b;
            v.push_back({a, b});
        }
        solve(0, 0);
        printf("%.6lf\n", sqrt(ans));
    }
}