[BOJ] 1007번: Vector Matching

https://www.acmicpc.net/problem/1007

만약 벡터를 매칭할 수 있는 모든 경우에 대해 합을 구하려고 들면 대략 $20!/(10! \times 2^{10}) = 654,729,075$ 가지에 대해 확인을 해야하기 때문에 구현을 정말 잘 하지 않는 이상 시간초과가 거의 무조건 발생할 것입니다. 대신, 한 가지 성질을 활용하면 조사해야하는 가지수를 줄일 수 있습니다.

그 성질은 다음과 같습니다.

$v1$ = 선분 AB, $v2$ = 선분 CD라고 할 때 두 벡터 $v1$, $v2$의 합은 B의 좌표+D의 좌표-A의 좌표-C의 좌표이다.

 즉, 내가 임의로 $N/2$개의 점을 시작점으로 정하고 $N/2$개의 점을 도착점으로 정했을 때 도착점들의 좌표를 다 더하고 시작점의 좌표를 전부 빼고나면 벡터의 합을 찾을 수 있습니다. $N$이 최대 20이고 $\binom{20}{10}$은 20만이 채 안되기 때문에 전수조사를 별 무리없이 할 수 있습니다.

https://github.com/encrypted-def/BOJ/blob/master/1007.cpp