import sys
input = sys.stdin.readline
from itertools import combinations
import math
INF = 10**9
T = int(input())
for test in range(T):
N = int(input())
xlist = []
ylist = []
for i in range(N):
x,y = map(int,input().split())
xlist.append(x)
ylist.append(y)
xsum = sum(xlist)
ysum = sum(ylist)
result = INF
for select in combinations(range(N),N//2):
xsum1 = xsum
ysum1 = ysum
for i in select:
xsum1 -= xlist[i]*2
ysum1 -= ylist[i]*2
result = min(result,math.sqrt(xsum1**2+ysum1**2))
print(result)
수학적 배경지식이 있다면 너무나 쉽게 풀 수 있는 문제
결국 N개의 점에서 N/2개의 벡터의 합이라는 뜻은, +로 잡을 점 N/2개와 -로 잡을 점 N/2개를 구하고 모두 합해버리면 된다는 뜻이다.
즉 combinations을 이용해 nCn/2 를 써서 어떤 점을 음수로 잡을지를 정한 뒤 최솟값을 구하면 된다.
다른 사람들의 풀이를 보니 문제의 의도는 백트래킹을 이용한 브루트포스 알고리즘으로 풀라고 낸 문제인 것 같은데, 이 부분에 대해서도 고려해봐야겠다.
여담으로 이 문제는 python으로 채점했을때와 pypy로 채점했을때 시간이 무려 20배나 차이가 났는데, 어디서 이런 차이가 오는건지 궁금하다.
오늘의 교훈) 수학이 중요하다