[BaekJoon] 1007 벡터 매칭 (Java)

1.  문제 링크

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

2.  문제

요약

• 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 합니다.
• 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합입니다.
• P에 속하는 모든 점은 한 번씩 쓰여야 합니다.
• 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반입니다.
• 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스의 첫 번째 줄에 20보다 작거나 같은 자연수인 점의 개수 N이 주어집니다. 두 번째 줄부터 N개의 줄에 절댓값이 100,000보다 작거나 같은 정수인 점의 좌표가 주어집니다.
  • 모든 점은 서로 다릅니다.
• 출력: 각 테스트 케이스마다 정답을 출력합니다. 절대/상대 오차는 $10^{-6}$까지 허용합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    
    static int N;
    static double answer;
    static int[][] points;
    static boolean[] visited;
    
    static void input() {
        N = scanner.nextInt();
        points = new int[N][2];
        visited = new boolean[N];
        
        for(int idx = 0; idx < N; idx++) {
            points[idx][0] = scanner.nextInt();
            points[idx][1] = scanner.nextInt();
        }
    }
    
    static void solution() {
        answer = Double.MAX_VALUE;
        
        choosePoints(0, 0);
        
        sb.append(answer).append('\n');
    }
    
    static void choosePoints(int index, int count) {
        if(count == N / 2) {
            answer = Math.min(answer, getVectorAmount());
            return;
        }
        
        for(int idx = index; idx < N; idx++) {
            if(!visited[idx]) {
                visited[idx] = true;
                choosePoints(idx + 1, count + 1);
                visited[idx] = false;
            }
        }
    }
    
    static double getVectorAmount() {
        int x = 0, y = 0;
        
        for(int idx = 0; idx < N; idx++) {
            if(visited[idx]) {
                x += points[idx][0];
                y += points[idx][1];
            } else {
                x -= points[idx][0];
                y -= points[idx][1];
            }
        }
        
        return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
    }
    
    public static void main(String[] args) {
        int T = scanner.nextInt();
        
        while(T-- > 0) {
            input();
            solution();
        }
        
        System.out.print(sb);
    }
    
    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}