Hide

Problem B
Circuit Counting

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

Suppose you are given a sequence of $N$ integer-valued vectors in the plane $(x_ i,y_ i)$, $i = 1, \ldots , 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

\[ \begin{array}{l} \{ (1,2), \; (-1,-2) \} \\ \{ (1,1), \; (-1,-1) \} \\ \{ (1,2), \; (1, 1), \; (-2, -3) \} \\ \{ (1,2), \; (-1,-2), \; (1,1), \; (-1,-1) \} \end{array} \]

Input

Input begins with an integer $N \le 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| \le 10$ and $(x,y) \neq (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 $10^{10}$.

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

Please log in to submit a solution to this problem

Log in