BAEKJOON 1007 - Vector Matching

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

만약 (x1, y1), (x2, y2), (x3, y3), (x4, y4)  이란 점들이 있고 이 중

(x1, y1), (x3, y3)을 선택하여 벡터를 만들고 (x2, y2), (x4, y4) 를 선택해 벡터를 만들었다고 할 때,

첫 번째 벡터는 (x1 - x3, y1 - y3) 으로 표현할 수 있고 두 번째 벡터는 (x2 - x4, y2 - y4) 으로 표현할 수 있습니다.

그리고 두 벡터의 합은

(x1 + x2 - (x3 + x4) , y1 + y2 - (y3 + y4)) 이라 할 수 있습니다. 

여기서 만약 x1 + x2 + x3 + x4 를 미리 구해두고

벡터가 되는 점의 한 쪽들을 선택하며 그 점들의 x 좌표들을 구해둔다면

즉 예에서는 x1 + x2 를 구해둔다면 x1 + x2 - (x3 + x4) 을 

x의 전체 합 - 2 * (x1 + x2) 으로 손쉽게 구할 수 있습니다.

위 방법과 n 개의 점에서 n/2 개의 점을 순서에 상관없이 고르는 방법을 통해 해당 문제를 풀었습니다. (가짓수는 이항 계수가 되겠지요)

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip> 
using namespace std;
typedef long long ll;
 
struct Pos
{
    int x, y;
};
 
int n;
ll _sumX, _sumY;
vector<Pos> points;
 
 
double bruteForce(int start, int remaining, int sumX, int sumY, vector<int>& selected)
{
    if (remaining == 0)
        return sqrt(pow(_sumX - sumX * 2, 2) + pow(_sumY - sumY * 2, 2));
        
    double ret = -1;
    for (int i = start; i <= points.size() - remaining; ++i)
    {
        selected.push_back(i);
        double candidate = bruteForce(i + 1, remaining - 1, sumX + points[i].x, sumY + points[i].y, selected);
        if (candidate < ret || ret == -1)
            ret = candidate;
        selected.pop_back();
    }
    return ret;
}
 
 
int main()
{
    int cases;
    cin >> cases;
 
    for (int i = 0; i < cases; i++)
    {
        points.clear();
        _sumX = _sumY = 0;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            _sumX += x;
            _sumY += y;
 
            Pos pos;
            pos.x = x;
            pos.y = y;
            points.push_back(pos);
        }
 
        vector<int> temp;
        cout << fixed << setprecision(6) << bruteForce(0, n / 2, 0, 0, temp) << endl;
    }
 
    return 0;
}