[백준] 1007 벡터 매칭 [자바]

 

---

https://blog.itcode.dev/posts/2021/06/09/a1007

[백준 / JAVA] 백준 알고리즘 1007번 벡터 - 𝝅번째 알파카의 개발 낙서장

 

좌표 (x1, y1), (x2, y2), (x3, y3), (x4, y4) 가 있으며, 좌표에서 두 벡터인 v1, v2를 구한다.

    v1 = (x2-x1, y2-y1)

    v2 = (x4-x3, y4-y3)

벡터의 합은 두 벡터의 단순합으로 이루어진다.

 

벡터의 총합 v는

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	static int[][] P;
	static boolean[] positive;
	static double min;
 	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			int n = Integer.parseInt(br.readLine());
			P = new int[n][2];
			for(int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				P[i][0] = x; //x좌표
				P[i][1] = y; //y좌표
			}
			positive = new boolean[n];
			min = Double.MAX_VALUE;
			combination(0, n/2); //n/2개의 양의 좌표를 구한다
			System.out.println(min);
		}
	}
 	static void combination(int index, int cnt) {
 		if(index == P.length)
 			return;
 		if(cnt == 0) {
 			min = Math.min(min, getVector());
 		}
 		for(int i = index; i < P.length; i++) {
 			positive[i] = true; //양수 좌표 v = v1 + v2 = (x2+x4-x1-x3, y2+y2-y1-y3)
 			combination(i+1, cnt-1);
 			positive[i] = false;
 		}
 	}
 	static double getVector() {
 		double result = 0;
 		int sum_x = 0;
 		int sum_y = 0;
 		for(int i = 0; i < P.length; i++) {
 			if(positive[i]) {
 				sum_x += P[i][0];
 				sum_y += P[i][1];
 			}
 			else {
 				sum_x -= P[i][0];
 				sum_y -= P[i][1];
 			}
 		}
 		result = Math.sqrt(Math.pow(sum_x, 2) + Math.pow(sum_y, 2));
 		return result;
 	}
}