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

http://wwww.acmicpc.net/problem/1007

 

 

# 조건

• 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자.
• 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다.
• 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.
• 벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.
• 평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

 

# 접근 방법

• 우선 벡터를 구하는 방법
  • v1 = (x2-x1, y2-y1)
  • v2 = (x4-x3, y4-y3)
• 벡터 사이의 합은
  • v1 + v2 = (x2+x4 -x1-x3, y2+y4 -y1-y3)
  • |v1 + v2| = sqrt((x2+x4 -x1-x3)^2 + (y2+y4 -y1-y3)^2)
• 이 때, 위의 벡터 사이의 합 공식을 x와 y를 나눠서 본다면
• 각각 2개는 더하고 2개는 뺄 수 있다.
• 즉, 벡터들의 끝 지점에 있는 점들을 모두 합한 것과, 시작 지점에 있는 점들을 모두 뺀 것이 N개의 점으로 만든 N/2 개의 벡터들을 합하여 만든 벡터의 값과 같다
• v1 + v2 + v3 + ... + vN/2 = (x2+x4+x6+...+xN -x1-x3-x5...-xN-1,y2+y4+y6+...+yN -y1-y3-y5...-yN-1)
• N이 20까지만 주어지기 때문에, 전체 탐색 후 최소값을 구해도 된다.
• sum_dot 함수를 이용해 선택된 점의 좌표들을 더해준다.
• 10개의 점을 고르는 경우의 수를 조합으로 구한 후
• 빼야하는 절반의 점들의 좌표합을 더하고 나머지 점들의 좌표합을 빼서 구해주면 된다.
• 이 때, 전체 합에서 절반의 점들의 값을 안빼주고 계산하는 경우 절반의 점 값의 합을 x 2 해주어야 한다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  
  
def sum_dot(mat):  
    res = [0,0]  
    for i in mat:  
        res[0] += i[0]  
        res[1] += i[1]  
    return res  
  
T = int(input())  
  
for _ in range(T):  
    N = int(input())  
    dot = [[*map(int, input().split())] for _ in range(N)]  
    total_sum = sum_dot(dot)  
    result = sys.maxsize  
    # 빼줄 점들 구하기  
    minus_dot = list(combinations(dot, N//2))  
    for i in minus_dot:  
        cur = sum_dot(i)  
        # 전체 좌표에서 빼주지 않았으므로 현재 구하는 합도 *2를 해준다.  
        result = min(result, ((2*cur[0] - total_sum[0])**2 + (2*cur[1] - total_sum[1])**2)**0.5)  
  
    print(result)