회로 세기

시간 제한2초메모리 제한256 MB

요약

주어진 최대 40개 평면 벡터 가운데 합이 영벡터가 되는 비어 있지 않은 부분집합 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 분할 정복, 해시맵
정답자: 아직 제출이 없습니다

문제

평면 위의 정수 벡터 $N$ 개 $(x_i, y_i)$ 가 순서대로 주어진다. 원점에서 출발해 각 벡터를 직전 위치에서의 변위로 삼으면 경로 하나가 만들어진다. 예를 들어 벡터 (1, 2), (2, 3), (-3, -5)는 경로 (0, 0), (1, 2), (3, 5), (0, 0)을 만든다. 원점에서 끝나는 경로를 회로라고 하며, 방금 만든 경로는 회로다.

비어 있지 않은 아무 부분집합으로나 경로를 만들 수 있고, 그 경로가 회로인지 아닌지는 부분집합을 어떤 순서로 이어 붙이든 달라지지 않는다. 회로가 되는 부분집합이 몇 개인지 세어라.

예를 들어 벡터가 {(1, 2), (-1, -2), (1, 1), (-2, -3), (-1, -1)}이면 회로가 되는 부분집합은 다음 4개다.

{(1, 2), (-1, -2)}
{(1, 1), (-1, -1)}
{(1, 2), (1, 1), (-2, -3)}
{(1, 2), (-1, -2), (1, 1), (-1, -1)}

입력

첫째 줄에 벡터의 개수 $N$ 이 주어진다. ( $1 \le N \le 40$ )

다음 $N$ 개 줄에 각각 정수 $x$ 와 $y$ 가 공백으로 구분되어 주어지며, 벡터 $(x, y)$ 를 나타낸다. ( $|x| \le 10$ , $|y| \le 10$ , $(x, y) \ne (0, 0)$ )

주어지는 벡터는 모두 서로 다르다.

출력

회로가 되는, 비어 있지 않은 부분집합의 개수를 출력한다. 답은 $10^{10}$ 보다 작음이 보장된다.

예제6

예제 1
입력
```
5
1 2
1 1
-1 -2
-2 -3
-1 -1
```
예상 출력
```
4
```
예제 2
입력
```
1
10 -10
```
예상 출력
```
0
```
예제 3
입력
```
2
4 -7
-4 7
```
예상 출력
```
1
```
예제 4
입력
```
2
1 0
0 1
```
예상 출력
```
0
```
예제 5
입력
```
8
1 1
2 3
3 5
4 7
5 9
10 10
7 2
6 6
```
예상 출력
```
0
```
예제 6
입력
```
3
3 4
-5 1
2 -5
```
예상 출력
```
1
```