(Baijun) Issue 1007 Vector Matching-PYTHON 벡터 매칭

(Baijun) Issue 1007 Vector Matching-PYTHON 벡터 매칭

Byissue

(Baijun) Issue 1007 Vector Matching-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)



Similar Posts