Hide

Problem C
Circuit Counting

/problems/countcircuits/file/statement/en/img-0001.png

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

Input begins with an integer N40 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)(0,0). Since the given vectors are a set, all vectors are unique.

Output

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

Sample Input 1 Sample Output 1
5
1 2
1 1
-1 -2
-2 -3
-1 -1
4
Hide

Please log in to submit a solution to this problem

Log in