[BOJ] 1007번 - 벡터 매칭

백준 1007번 - 벡터 매칭

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	5416	1860	1334	35.366%

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

V에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 ${10^{-6}}$까지 허용한다.

 

---

예제 입력 1

2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000

예제 출력 1

0.000000000000
282842.712474619038

출처

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

1007번: 벡터 매칭

알고리즘 분류

• 수학
• 브루트포스 알고리즘

접근 방법

문제를 잘 읽어보면, 평면 상의 N개의 점 중 절반은 시점, 나머지 절반은 종점이 되는 것을 알 수 있다. 그에 따라 N은 짝수개가 주어진다.

우리가 구하고자 하는 것은 벡터 매칭에 있는 벡터의 합의 길이의 최솟값이다.

(시점, 종점) 이 구분되는 k번째 벡터를 ${v_k}$ 라고 표현하자. ${v}$의 개수는 N/2개가 존재하며 이를 구하는 가장 Naive한 방법은 각 벡터의 시점과 종점에 사용될 수 있는 점들을 무작정 대입하는 방법이고, 이를 계산할 경우 O(N!)의 시간복잡도를 가지게 된다. 

문제에서 주어진 N의 범위는 최대 20이므로 20! 은 대략 2.4e18 의 수이므로 시간 내에 모든 연산을 하는 것은 불가능하다.

 

그런데, 문제를 잘 읽어보면 벡터의 합의 길이의 최솟값을 구하는 것이 목표이고, 벡터의 합을 구하기 위해 특정 벡터의 성분값을 알아야한다는 것을 알 수 있다. 특정 벡터의 성분은 (종점의 x좌표 - 시점의 x좌표, 종점의 y좌표 - 시점의 y좌표) 로 표현할 수 있다.-> [시점을 (0,0)원점으로 평행이동]

즉 벡터의 합의 성분 (x, y) = ( ${ \sum_{i=1}^{N/2} {종점_k의 x좌표 - 시점_k의 x좌표} }$, ${\sum_{i=1}^{N/2}{종점_k의 y좌표 - 시점_k의 y좌표}}$) 로 표현되는 것을 알 수 있다.

 

이와 같은 사실을 알면, N/2개의 시점을 결정하면 나머지 N/2개의 종점이 자동으로 결정이 되고 종점으로 시점으로 결정한 성분들을 빼준 다음 합한다면 (N/2)! 의 시간 안에 문제를 해결 할 수 있다.

소스 코드

#define ll long long
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<ll,ll>> v;
bitset<21> selected;
pair<ll, ll> ans = {1e7, 1e7};

void select(int rest, int idx){
    if( rest == 0 ){
        // selected가 false 인 것을 종점(to)라고 정의
        pair<ll, ll> ret = {0, 0};
        for(int i=0; i<N; i++){
            if( selected[i] ){
                ret.first -= v[i].first;
                ret.second -= v[i].second;
            }
            else{
                ret.first += v[i].first;
                ret.second += v[i].second;
            }
        }
        if( ret.first * ret.first + ret.second * ret.second <
                ans.first * ans.first + ans.second * ans.second ){
            ans.first = ret.first;
            ans.second = ret.second;
        }
        return;
    }
    for(int i=idx; i<N; i++){
        if(selected[i])
            continue;
        selected[i] = true;
        select(rest-1, i+1);
        selected[i] = false;
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T;
    cin >> T;
    cout.precision(7);
    cout << fixed;

    while(T--){
        cin >> N;
        v.resize(N), selected.reset();
        ans = {1e7, 1e7};

        for(int i=0; i<N; i++){
            cin >> v[i].first >> v[i].second;
        }
        select(N/2, 0);
        cout << sqrt( ans.first * ans.first + ans.second * ans.second ) << '\n';
    }
    return 0;
}