[백준 1007] 벡터 매칭 - 백트래킹

1007번: 벡터 매칭

전형적인 백트래킹 응용문제이다.

$N$개의 좌표에서 $N/2$개의 x, y좌표 값에는 +를 붙이고, $N/2$개에는 -를 붙인다.

여기서 +를 붙인 좌표들은 벡터의 끝점들이고, -를 붙인 좌표들은 벡터의 시작점들이다.

이 시작점과 끝점들이 어떻게 연결되어 있는지는 길이와 관련이 없다는 점을 알고 있어야 한다.

그 후 $x$좌표와 $y$좌표를 모두 합한 후, $\sqrt{x^2+y^2}$를 계산한다.

경우의 수는 ${}_N\mathrm{C}_{N/2}$개이고, 이들 중 가장 작은 값을 구하면 된다.

참고로 $N = 20$일 때 ${}_{20}\mathrm{C}_{10} = 184756$이다.

아래 소스코드가 이해되지 않는다면 https://bangk00.tistory.com/6 를 보면 된다.

<소스 코드>

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

double min1;
void selectminus(vector<pair<int,int>>&coor, vector<int>& picked, int n, int topick, int sumx, int sumy) {
    if (topick == 0) {
        long long x = sumx; long long y = sumy;
        double result = sqrt(x*x+y*y);
        if (min1 > result) min1 = result;
        return;
    }
    int smallest = picked.empty() ? 0 : picked.back()+1;
    for (int i = smallest; i < n; i++) {
        picked.push_back(i);
        selectminus(coor, picked, n, topick-1, sumx-2*coor[i].first, sumy-2*coor[i].second);
        picked.pop_back();
    }
}

int main() {
    int tc;
    scanf("%d", &tc);
    for (int i = 0; i < tc; i++) {
        min1 = 2147483647;
        int n;
        scanf("%d", &n);
        vector<pair<int, int>> coor;
        vector<int> picked;
        int sumx = 0; int sumy = 0; int x,y;
        for (int j = 0; j < n; j++) {
            scanf("%d %d", &x, &y);
            coor.push_back(make_pair(x,y));
            sumx+=x; sumy+=y;
        }
        selectminus(coor, picked, n, n/2, sumx, sumy);
        printf("%.11lf\n", min1);
    }
}

이 때의 시간복잡도는 $TC*O({}_N\mathrm{C}_{N/2})$ 이다.