👀 문제 사이트 : https://www.acmicpc.net/problem/1007
이 문제는 짝수 개의 좌표가 주어지면 그 중 절반을 시작점으로 잡고 남은 절반은 끝점으로 잡아 벡터를 만들어주고 그 벡터들의 합의 최솟값을 구하는 문제이다.
문제 풀이에서 핵심은 (끝점들의 x, y값들의 합 - 시작점들의 x, y값들의 합) 으로 한번에 벡터들의 합의 최솟값을 구하는 것이다. 따라서 시작점들을 뽑아 미리 x, y좌표들의 합을 구해놓고 계산만 진행하면 문제를 풀 수 있다.
조합을 이용하여 주어진 좌표 중 절반을 뽑아 시작점으로 잡았고, 처음 좌표들을 입력받을 때 x, y 좌표들을 모두 합한 값들을 저장하여 (총합 - 시작점들의 합) 으로 끝점들을 바로 구하였다.
python에는 combinations라는 함수가 있어 해당 함수를 사용하였다.
from itertools import combinations
import sys
input = sys.stdin.readline
t = int(input())
results = []
for _ in range(t):
n = int(input())
graph = []
total_x = 0
total_y = 0
for _ in range(n):
x, y = map(int, input().split())
graph.append([x, y])
total_x = total_x + x
total_y = total_y + y
vertex = list(combinations(graph, n//2))
result = int(1e9)
for ve in vertex:
x1, y1 = 0, 0
for v in ve:
x1 = x1 + v[0]
y1 = y1 + v[1]
x2 = total_x - x1
y2 = total_y - y1
result = min(result, ((x1-x2)**2 + (y1-y2)**2) ** 0.5)
results.append(result)
for r in results:
print(r)