백터 매칭

• 문제

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

1007번: 벡터 매칭

 

• 코드

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

bool his[20];
int N;
long double res = 400020;

vector<pair<int,int>> points;

void dfs(int cur_idx, int left){

    if(left == 0){
        long double x_val = 0; long double y_val = 0;
        for(int i=0; i<points.size(); i++){
            if(his[i]){
                x_val += points[i].first;
                y_val += points[i].second;
            }else{
                x_val -= points[i].first;
                y_val -= points[i].second;
            }
        }
        long double tmp = (long double)sqrt(x_val*x_val+y_val*y_val);
        if(tmp < res){
            res = tmp;
        }
    }else if(cur_idx < N){
        his[cur_idx] = true;
        dfs(cur_idx+1, left-1);
        his[cur_idx] = false;
        dfs(cur_idx+1, left);
    }

}

int main(){
    int T;
    cin >> T;
    cout.precision(12);
    while(T--){
        cin >> N;
        for(int i=0; i<N; i++){
            int x, y;
            cin >> x >> y;
            points.push_back({x, y});
        }
        dfs(0,N/2);
        cout << fixed <<  res << '\n';

        points.clear();
        for(int i=0; i<20; i++)
            his[i] = false;
        res = 400000;
    }

}

• 피드백
  • 1시간 반 걸림
  • 처음에는 문제의 설명 그대로 두 점을 매칭시키고 그 것의 방향을 고려해서 짜줬더니 시간초과가 났다.
    • 복잡도는 nCn/2 * (n/2)! * 2^(n/2)가 나올 것... 그냥 시간초과가 남
  • 생각을 해보니 벡터는 Pa - Pb이다. 즉 점의 반 개를 - 부호를 취해줘서 끝에서 합하면 그만
  • 곧 nCn/2의 문제로 변함...  20C10 = 184756 으로 풀 수 있다.
  • 실수로 조합구하는 법을 까먹어서 외부 코드를 참고... 조합은 위처럼 선형으로 구할 수 있다.