SWEA 1494. 사랑의 카운슬러(Python)(D4)

N마리의 지렁이가 있으면 이중 N/2마리를 출발지렁이, N/2를 도착지렁이로 구분짓는다.
그리고 출발지렁이의 좌표값합과 도착지렁이의 좌표값합을 A, B라고 할 경우
(Ax-Bx)^2+(Ay-By)^2가 최소가 되게하는 지렁이 조합의 경우의수를 찾으면 됨
한쌍, 한쌍 구해서 계산할 필요가 없다. 전체벡터합을 더해 벡터의크기를 구하기 때문!
제곱하고 난 뒤 더하므로 부호계산 할 필요 없음!
ex) (2,3) (5,6) (3,-2) (6,-5)

• 1-3, 2-4 매칭
  -> (2,3) - (3,-2) = (-1,5) / (5,6) - (6,-5) = (-1,11)
  벡터의 크기 = (-1,5)+(-1,11)=(-2,16) -> 4 + 256 = 260
  -> (2,3) + (5,6) - (3,-2)- (6,-5) = (-2,16)
  벡터의 크기 = (-2,16) -> 4+256 = 260
• 1-2, 3,4 매칭
  -> (2,3)-(5,6)=(-3,-3) / (3,-2)-(6,-5)=(-3,3)
  벡터의 크기 = (-3,-3) + (-3,3) = (-6,0) -> 36
  -> (2,3) + (3,-2) - (5,6) - (6,-5) = (-6,0)
  벡터의 크기 =(-6,0) -> 36
  그러므로, 백트래킹으로 N마리의 지렁이중 N/2마리를 중첩되지 않는 조합을 찾는다!
  그리고 각 경우의 수마다 최소값 비교!

res=[]
def comb(vi,idx,su):
    if su==N/2:
        mat(vi)
        return
    for i in range(idx,N):
        vi[i]=1
        comb(vi,i+1,su+1)
        vi[i]=0

def mat(vi):
    global tmp
    A=[0,0]
    B=[0,0]
    for i in range(N):
        if vi[i]:
            A[0]+=li[i][0]
            A[1]+=li[i][1]
        else:
            B[0]+=li[i][0]
            B[1]+=li[i][1]
    tmp=min(tmp,(B[0]-A[0])**2+(B[1]-A[1])**2)

for m in range(int(input())):
    tmp=10**15 # 초기값을 꽤 크게 잡아야 한다.
    N=int(input())
    li=[]
    for i in range(N):
        li.append(list(map(int,input().split())))
    comb([0]*N,0,0)
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))