(Baijun) Issue 1007 Vector Matching-PYTHON 벡터 매칭
(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)
