1007번: Vector Matching

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


$O(tn{n \choose n/2})$

n/2개의 백터합을 풀어 쓰면 n/2개의 좌표는 더하고 n/2개의 좌표는 빼야 함을 알 수 있다.
모든 경우를 따져서 최소의 벡터 크기를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 20;
bool b[MAX_N];
int n, t, x[MAX_N], y[MAX_N];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d %d", x + i, y + i);
        for (int i = 0; i < n / 2; i++) b[i] = 0, b[i + n / 2] = 1;
        double r = 1e15, sx, sy;
        do {
            sx = sy = 0;
            for (int i = 0; i < n; i++) sx += (1 - b[i] * 2)*x[i], sy += (1 - b[i] * 2)*y[i];
            r = min(r, sqrt(sx*sx + sy*sy));
        } while (next_permutation(b, b + n));
        printf("%lf\n", r);
    }
    return 0;
}