[백준] 1007 벡터 매칭

1007번: 벡터 매칭

문제 확인

 

벡터의 특성과 벡터를 선택하는 조합 문제입니다.

 

풀이

 

문제에서 주의해야 할 점은 벡터의 합의 길이이므로 (0, 10), (0, -10) 벡터의 합은 (0, 0)이므로 길이는 0이 됩니다.

따라서 벡터의 합을 구할 때 단순히 sqrt((x1 - x2)^2 + (y1 - y2)^2)로 구하면 틀리게 됩니다.

 

전체 벡터 합을 구한 후 선택한 벡터들의 차를 이용하여 벡터의 합을 빠른 시간에 구할 수 있습니다.

(x1, y1), (x2, y2) ... (x10, y10)

total = (x1 + x2 + ..+.. + x10, y1 + y2 + .. + y10) => N/2개 선택 : total - (v ...)

= (x1 + x2 .. x5 - x6 - x7 .. x10, (y1 + y2 .. x5 - y6 - y7 .. y10)

해당 과정을 조합을 구하는 dfs를 통해 뺄 점들을 N/2개 선택하면 됩니다.

 

코드

#include <cstdio>
#include <cmath>
 
typedef struct pir {
    int x, y;
};
pir ary[20], total;
int n;
double mn;
void dfs(int cur, int idx, int x, int y) {
    if (cur) {
        for (int i = idx; i <= n - cur; i++)
            dfs(cur - 1, i + 1, x + ary[i].x, y + ary[i].y);
        return;
    }
    double t = sqrt(pow(total.x - (x << 1), 2) + pow(total.y - (y << 1), 2));
    if (t < mn)mn = t;
 
}
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        total = {}; mn = 1e308;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &ary[i].x, &ary[i].y);
            total.x += ary[i].x;
            total.y += ary[i].y;
        }
        dfs((n >> 1) - 1, 1, ary[0].x, ary[0].y);
        printf("%.7lf\n", mn);
    }
}