문제2684--Circuit Counting

2684: Circuit Counting

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 1  통과: 1
[제출] [채점기록] [묻고답하기]

문제 설명

Suppose you are given a sequence of N integer-valued vectors in the plane (xi, yi), i = 1, . . . , N. Beginning at the origin, we can generate a path by regarding each vector as a displacement from the previous location. For instance, the vectors (1, 2), (2, 3), (−3, −5) form the path (0, 0),(1, 2),(3, 5),(0, 0). We define a path that ends at the origin as a circuit. The example just given is a circuit. We could form a path using any nonempty subset of the N vectors, while the result (circuit or not) doesn’t depend on the ordering of the subset. How many nonempty subsets of the vectors form circuits?

For instance, consider the vectors {(1, 2),(−1, −2),(1, 1),(−2, −3),(−1, −1)} From these vectors we can construct 4 possible subset circuits using

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

입력 설명

Input begins with an integer N ≤ 40 on the first line. The next N lines each contain two integer values x and y forming the vector (x, y), where |x|, |y| ≤ 10 and (x, y) 6= (0, 0). Since the given vectors are a set, all vectors are unique.

출력 설명

Output the number of nonempty subsets of the given vectors that produce circuits. It’s guaranteed that the answer is less than 1010.

입력 예시 Copy

5
1 2
1 1
-1 -2
-2 -3
-1 -1

출력 예시 Copy

4

출처/분류