[백준]#1007 백터 매칭

문제

평면 상에 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

풀이

이 문제는 dfs(깊이 우선 탐색) 알고리즘을 이용해서 풀 수 있었다. 추가로 수학적인 문제 해결이 필요한데 벡터 합을 구하기 위해 전체 벡터 합을 구한 뒤 N/2개의 점을 정해서 빼준 뒤 벡터의 길이를 구하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] x_arr;
    static int[] y_arr;
    static int N;
    static double min;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            N = Integer.parseInt(br.readLine());
            x_arr = new int[N];
            y_arr = new int[N];
            min = Double.MAX_VALUE;
            long sum_x = 0;
            long sum_y = 0;

            for(int j=0; j<N; j++) {
                String[] input = br.readLine().split(" ");
                int x = Integer.parseInt(input[0]);
                int y = Integer.parseInt(input[1]);
                x_arr[j] = x;
                y_arr[j] = y;

                sum_x += x;
                sum_y += y;
            }

            dfs(sum_x, sum_y, 0, 0);

            System.out.println(min);
        }
    }

    public static void dfs(long sum_x, long sum_y, int idx, int cnt) {
        if(N-idx+cnt<N/2) return;

        if(cnt==N/2) {
            min = Math.min(min, Math.sqrt(sum_x*sum_x+sum_y*sum_y));
            return;
        }

        for(int i=idx; i<N; i++) {
            long next_sumX = sum_x - 2*x_arr[i];
            long next_sumY = sum_y - 2*y_arr[i];

            dfs(next_sumX, next_sumY, i+1, cnt+1);
        }
    }
}