백준(BOJ) 1007 벡터 매칭(Python)

문제 내용.

 

그냥 하면 되는 문제.

벡터의 합의 길이를 구해야 하는데, 벡터 매칭의 모든 벡터의 합은 전체 점의 x, y값의 합에 랜덤하게 뽑은 10개 점의 x, y값의 합을 두 번 빼주면 된다. 두 점을 잇는 벡터는 한 점에서 다른 점을 뺀 값이기 때문이다.

이 때 itertools의 combinations를 이용해 20C10으로 전체 집합에서 뺄 점을 뽑아준 뒤 각각 비교하면 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

for _ in range(int(input())):
    n=int(input())
    x_sum=0
    y_sum=0
    L=[]
    for i in range(n):
        a,b=map(int,input().split())
        x_sum+=a
        y_sum+=b
        L.append([a,b])
    ans=10e9
    for X in combinations(L,n//2):
        x=0
        y=0
        for a,b in X:
            x+=a
            y+=b
        ans=min(ans,math.sqrt((x_sum-x*2)**2+(y_sum-y*2)**2))
    print(ans)

벡터의 합의 길이를 벡터의 길이의 합으로 보고 조금 헤맸던 문제.

국어가 안 된다.