P1444 [USACO1.3] Wormhole

Farmer John's high-energy physics experiment over the weekend backfired, causing $n$ wormholes to appear on the farm, which is a two-dimensional plane. No two wormholes are at the same position. According to his calculations, FJ knows the wormholes are paired up, forming $\dfrac{n}{2}$ pairs. For example, if wormholes $A$ and $B$ form a pair, any object entering wormhole $A$ will exit from wormhole $B$ with its direction unchanged, and vice versa. However, this can lead to a rather unpleasant consequence. For instance, suppose there are two paired wormholes $A(1,1)$ and $B(3,1)$, and Bessie starts at $(2,1)$ moving in the positive $x$ direction. Bessie will enter wormhole $B(3,1)$, exit from $A(1,1)$, then enter $B$ again, getting trapped in an infinite loop! FJ knows the exact position of every wormhole on his farm. He knows Bessie always moves in the positive $x$ direction, although he does not remember Bessie's current position. Please help FJ count how many pairing schemes of wormholes have the property that there exists a position such that if Bessie starts there, she will be trapped in an infinite loop.

The first line contains a positive integer $n$, the number of wormholes. Each of the next $n$ lines contains two integers $x, y$, the coordinates of a wormhole.

Output a single integer, the answer.

### Constraints For 100% of the testdata, $2 \le n \le 12$, $0 \le x,y \le 10^9$. It is guaranteed that $n$ is even. ### Sample Explanation Number the wormholes $1$ to $4$. If we pair $1,2$ and $3,4$, then if Bessie starts anywhere between $(0,0)$ and $(1,0)$, she will fall into an infinite loop. Similarly, with the same starting point, if the pairings are $1,3$ and $2,4$, Bessie will also be trapped in a loop. (If Bessie enters through $3$ and exits from $1$, she will move toward $2$, then be teleported to $4$, and finally return to $3$.) Only the pairing $1,4$ and $2,3$ allows Bessie to walk in the positive $x$ direction from any point in the plane without entering an infinite loop. Problem statement translation from NOCOW. Translated by ChatGPT 5