%2021. 11. 5. 14:39에 작성된 글입니다%
https://www.acmicpc.net/problem/1007
1007번: 벡터 매칭
평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속
www.acmicpc.net
풀어보려고 전부터 꽤 노력했는데 결국 고등학교 기하를 배우고 나서야 풀 수 있었다. 벡터의 성질을 맨바닥에서 끄집어낼 수준의 머리는 안 되는 모양이다.
주어진 점을 각각 \(P_1, P_2, P_3... P_n\)이라고 하자.
임의의 점 P를 하나 잡고, \(\overrightarrow{PP_1}, \overrightarrow{PP_2}, \overrightarrow{PP_3}, ... , \overrightarrow{PP_n}\) 벡터를 생각하자.
여기서 벡터 \(\frac{n}{2}\)개의 방향을 뒤집으면 문제에서 요구하는 꼴의 선택 모양이 나온다는 것을 알 수 있다.
\(P\)를 \((0, 0)\)로 잡아서 간단하게 구현하면 된다.