[BOJ] 1007번. Vector Matching

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

문제명	Vector Matching
설 명	문제	평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 Vector Matching은 벡터의 집합인데, 모든 벡터는 집합 P 중 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터들의 집합이다. 또, P속의 모든 점은 모두 단 한번만 쓰여야 한다.   V에 있는 벡터의 개수는 P에 있는 점의 절반이다.   평면 상의 점이 주어졌을 때, 집합 P의 Vector Matching에 있는 벡터들의 합의 길이의 최소값을 출력하는 프로그램을 작성하시오.
	입력	첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.   첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.
	출력	각 테스트 케이스 마다 소수점 7자리에서 반올림하여 정답을 출력한다. (구한 답이 0이어도 0.000000 을 출력해야 한다.)

입력 예시

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

출력 예시

0.000000 282842.712475

---

이번 문제 풀면서 한 실수.

1. 문제 제대로 읽지 않아서 소수점 7자리까지 출력해서 계속 오답이 출력된 것.

2. dfs 함수 재귀타고 들어갈 때, 올바르지 않은 인자값을 넣어준 것.

   dfs(vec + arVec[i], pos + 1, cnt + 1); → dfs(vec + arVec[i], i + 1, cnt + 1); 로 수정.

---

고칠 점

1. 최근 숙지한 Class, 동적할당을 활용하는 것은 좋았으나, 원래 짜던대로 그냥 동적할당이 아닌, 그냥 정적으로 사이즈를 정해놓고 짯으면 코드량이 줄어 더 빨리 짤 수도 있었을 듯. 다음부터 이런 문제는 그냥 정적으로 짜도 상관 없을 듯.

---

느낀 점.

1. 사지방에서 Dev C++을 이용해서 문제푸는데, 디버깅도 안되서 머리를 많이 굴리면서 했던거 같다. 이렇게 계속 풀다보면 도움이 될 것 같다.

2. 이번에 깃허브 사용해서 올려볼까 했는데 사지방에서는 깃허브가 접속이 안된다고 한다ㅠ

---

문제 힌트.

그림과 같이 벡터 A - B는 벡터 A와 B 사이에 있는 벡터와 같다.

서로 다른 점 P1과 P2가 있다고 하자. P1에서 P2로 가는 벡터를 위의 방식으로 구하면

Vector (P0 to P1 ) - Vector (P0 to P2) = Vector (P1 to P2)

위와 같은 식이 완성된다. 여기서 Vector (P0 to P1)은 P1의 좌표값과 같으므로 다음과 같이 작성할 수 있다.

P1 - P2 = Vector (P1 to P2)

[사진출처]

http://www.kshitij-iitjee.com/Adding-Vectors-Subtracting-Vectors-equality-of-vectors

힌트 끝.

---

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
class Vector {
    public:
        double x;
        double y;
        
        Vector() {
            x = 0;
            y = 0;
        }
        
        void Input() {
            scanf("%lf %lf", &x, &y);
        }
        
        void Output() {
            printf("%d %d\n", x, y);
            system("pause");
        }
        
        Vector operator+(Vector a) {
            Vector vec;
            vec.x = this->x + a.x;
            vec.y = this->y + a.y;
            
            return vec;
        }
        
        Vector operator+=(Vector a) {
            this->x += a.x;
            this->y += a.y;
            
            return *this;
        }
        
        Vector operator-(Vector a) {
            Vector vec;
            vec.x = this->x - a.x;
            vec.y = this->y - a.y;
            
            return vec;
        }
        
        const double GetValue() {
            return sqrt(x * x + y * y);
        }
};
 
double dMin = -1;
int N = 0;
Vector *arVec = NULL, *totalVec = NULL, *tmpVec = NULL;
 
void dfs(Vector vec, int pos, int cnt) {
    
    if (cnt == N / 2) {
        Vector otherVector = *totalVec - vec;
        double dSOV = 0;
        
        dSOV = (otherVector - vec).GetValue(); //Sum Of Vector
        
        if (dSOV < dMin || dMin == -1)
            dMin = dSOV;
    }
    else {
        for (int i = pos ; i < N ; i ++)
            dfs(vec + arVec[i], i + 1, cnt + 1);
    }
}
 
int main() {
    int T = 0;
    
    scanf("%d", &T);
    
    while (T--) {
        scanf("%d", &N);
        
        arVec = new Vector[N];
        totalVec = new Vector;
        tmpVec = new Vector;
 
        
        for (int i = 0 ; i < N ; i ++) {
            arVec[i].Input();
            *totalVec += arVec[i];
        }
        
        dfs(*tmpVec, 0, 0);
        
        printf("%.6lf\n", dMin);
        
        delete[] arVec;
        delete totalVec, tmpVec;
        
        dMin = -1;
    }
}