1007. 벡터 매칭

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

1007번: 벡터 매칭

 

평면상의 좌표 N개가 주어지고, 점 2개씩 짝지어 벡터를 이룰 수 있다.

각 점들을 1번만 사용하고 2개씩 매칭하여 N/2 개의 벡터를 만들 수 있다.

이렇게 만든 N/2개의 벡터들을 다 더한 벡터의 길이가 최소가 되도록 만들면 된다.

 

 

sol1.

재귀 완전탐색으로 탐색하면서 벡터를 만들어 갔다.

현재 위치가 N이 되는 순간 벡터 요소의 제곱들의 합을 비교하여 최소값을 찾았다.

최적화를 한답시고 현재 보고있는 위치의 다음 위치들만 벡터 매칭의 후보로 두었다.

하지만 벡터를 만들 때 두 방향으로 만들 수 있기에 두번 작업을 해서 시간초과가 발생했다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int N;
 
pii mk_vec(pii a, pii b)
{
    return {b.first-a.first, b.second-a.second};
}
 
pii add(pii a, pii b)
{
    return {a.first+b.first, a.second+b.second};
}
 
pii rev_vec(pii a)
{
    return {-a.first, -a.second};
}
 
double get_length(pii a)
{
    return sqrt((double)a.first*a.first+a.second*a.second);
}
 
pii get_min(pii a, pii b)
{
    int ak = a.first*a.first+a.second*a.second;
    int bk = b.first*b.first+b.second*b.second;
    if(ak > bk) return b;
    return a;
}
 
bool check[22];
 
pii brute(int pos, vector<pii>& v, pii sum)
{
    if(pos == N)
    {
        return sum;
    }
    if(check[pos]) return brute(pos+1, v, sum);
    pii ret = {INT_MAX, INT_MAX};
    check[pos] = true;
    for(int i=pos+1;i<N;i++)
    {
        if(check[i] == false)
        {
            check[i] = true;
            pii vc = mk_vec(v[pos], v[i]);
            ret = get_min(ret, brute(pos+1, v, add(sum, vc)));
            ret = get_min(ret, brute(pos+1, v, add(sum, rev_vec(vc))));
            check[i] = false;
        }
    }
    check[pos] = false;
    return ret;
    
}
 
void solve()
{
    cin >> N;
    cout.precision(12);
    cout << fixed;
    memset(check, false, sizeof(check));
    vector<pii> v(N);
    for(int i=0;i<N;i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    pii ans = brute(0, v, {0, 0});
    cout << get_length(ans) << endl;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
    while(tc-- > 0)
    {
        solve();
    }
 
    return 0;
}

 

 

sol2.

벡터를 더할 때는 교환법칙이 성립한다. 즉, 더하는 순서는 상관없이 결과는 같다.

이를 이용하면 벡터를 따로 만드는 대신, 출발점과 도착점을 분리하여 연산할 수 있다.

 

두 점 a(x1, y1), b(x2, y2)에 대한 벡터(출발점 a, 도착점 b) v는 다음과 같이 계산할 수 있다.

v = (x2-x1, y2-y1)

두 벡터 ab (a(x1, y1), b(x2, y2)), cd  (c(x3, y3), d(x4, y4))의 합 v는 다음과 같다.

v = (x2-x1+x4-x3, y2-y1+y4-y3)

ab + cd 와 cd + ab 는 같은 결과를 가진다.

 

v를 출발점인 a, c와 도착점인 b, d로 나누어 생각하면 다음과 같이 계산할 수 있다.

v = (-x1-x3+x2+x4, -y1-y3+y2+y4)

이렇게 생각하면 N개의 점 중에 출발점 N/2 개를 고르고, 나머지 N/2 개는 도착점이 되어 크기가 최소가 되는 v를 찾는 문제가 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
int N;
bool check[22];
 
double get_length(vector<pii>& v)
{
    pii recv = {0, 0};
    for(int i=0;i<N;i++)
    {
        if(check[i])
        {
            recv.first -= v[i].first;
            recv.second -= v[i].second;
        }
        else
        {
            recv.first += v[i].first;
            recv.second += v[i].second;
        }
    }
    return sqrt(pow(recv.first, 2.0)+pow(recv.second, 2.0));
}
 
double brute(int pos, int cnt, vector<pii>& v)
{
    if(cnt == (N>>1))
    {
        return get_length(v);
    }
    double ret = DBL_MAX;
    for(int i=pos;i<N;i++)
    {
        check[i] = true;
        ret = min(ret, brute(i+1, cnt+1, v));
        check[i] = false;
    }
    return ret;
    
}
 
void solve()
{
    cin >> N;
    cout.precision(12);
    cout << fixed;
    memset(check, false, sizeof(check));
    vector<pii> v(N);
    for(int i=0;i<N;i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    cout << brute(0, 0, v) << endl;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
    while(tc-- > 0)
    {
        solve();
    }
 
    return 0;
}