[백준] 1007번 벡터 매칭 - 혼자만의 사랑

(백준) #1007 벡터매칭 – PYTHON 벡터매칭

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

#1007: 벡터 매칭

평면에는 N개의 점이 있고 P는 세트입니다.

세트 P의 벡터 일치는 벡터 세트이며 각 벡터는 세트 P의 한 지점에서 시작하여 다른 지점에서 끝납니다.

또한 P에서

'추천 관련글,

www.acmicpc.net

문제

평면에는 N개의 점이 있고 P는 세트입니다.

세트 P의 벡터 일치는 벡터 세트이며 각 벡터는 세트 P의 한 지점에서 시작하여 다른 지점에서 끝납니다.

또한 P에 속한 각 점은 한 번만 작성해야 합니다.

벡터 매칭의 벡터 수는 P의 포인트 수의 절반입니다.

평면의 주어진 점에 대해 집합 P의 벡터 비교에서 벡터 합의 최소 길이를 반환하는 프로그램을 작성하십시오.

기입

테스트 케이스의 수 T는 첫 번째 줄에 지정됩니다.

각 테스트 케이스는 다음으로 구성됩니다.

포인트 수 N은 테스트 케이스의 첫 번째 줄에 제공됩니다.

N은 짝수입니다.

점의 좌표는 두 번째 줄부터 시작하여 N 줄로 제공됩니다.

N은 20 이하의 자연수이고, 좌표는 절대값이 100,000 이하인 정수이다.

모든 포인트가 다릅니다.

누르다

각 테스트 케이스에 대한 정답을 출력하십시오. 절대/상대 오류는 10-6까지 허용됩니다.

알고리즘 분류

수학

무차별 대입 알고리즘

import sys, itertools
input=sys.stdin.readline
T=int(input())
for _ in range(T):
    N=int(input()) # 점의 개수
    points = () # 좌표의 리스트
    total_x,total_y = 0,0
 
    for _ in range(N):
        x,y = map(int,input().split())
        total_x +=x ; total_y += y # 모든 x의 합과 y의 합 저장
        points.append((x,y))
 
    comb = list(itertools.combinations(points, N//2))
    ans=3e5
    
    for c in comb(:len(comb)//2): # len(comb)는 항상 짝수
        x1,y1 = 0,0
        for x,y in c:
            x1 += x ; y1 += y
        x2,y2 = total_x-x1,total_y-y1 # x와 y를 x1,y1과 x2,y2 두 그룹으로 절반 나누기
        
        hab_vector = ((x2-x1)**2 + (y2-y1)**2)**(0.5) # 절반 나눈 두 그룹간의 합벡터
        ans=min(ans,hab_vector)
    print(ans)