[백준 파이썬] 1007 벡터 매칭

백준 1007

출처: OnlineMathLearning
점 A와 점 B를 잇는 벡터를 $\overrightarrow{AB}$라 한다면 이를 $\overrightarrow{OB} - \overrightarrow{OA}$ (O는 원점)으로 표현할 수 있다. 그렇다면 주어진 점들로 만든 벡터도 원점에서 출발하는 벡터로 바꿔줄 수 있고,

$\displaystyle\sum_{i=0}^{N/2}\overrightarrow{OB_i} - \overrightarrow{OA_i}$

를 계산하는 문제로 바꿀 수 있다. 모든 점 중 절반은 더하고 절반은 빼서 최종 벡터의 길이를 구하면 된다.

import math
from itertools import combinations

T = int(input())
results = []
for _ in range(T):

    N = int(input())
    coords = [list(map(int, input().split())) for _ in range(N)]

	# 모든 벡터들의 합
    coords_total_sum = list(map(sum, zip(*coords)))
    min_distance = 10**12

    for idx in combinations(range(N), r=N//2):
    	# 더해줄 벡터들의 합
        sums = list(map(sum, zip(*[coords[i] for i in idx])))
        # 모든 벡터들의 합에서 더해줄 벡터들을 빼면 빼줄 벡터들의 합만 남는다.
        subs = [coords_total_sum[0] - sums[0], coords_total_sum[1] - sums[1]]
		
        # 최종 벡터 계산
        fin_coords = [sums[0]-subs[0], sums[1]-subs[1]]
        # 거리 계산
        min_distance = min(min_distance, 
                        math.sqrt(fin_coords[0]**2 + fin_coords[1]**2))

        if min_distance == 0:
            break
    results.append(min_distance)    

print(*results, sep='\n')