Wormholes

Farmer John's weekend hobby of running high-energy physics experiments has backfired, and $N$ wormholes ($2 \le N \le 12$, $N$ even) have appeared on his farm. Each wormhole sits at a distinct point of the farm's 2D map.

By John's calculations the wormholes link up into $N/2$ pairs. If wormholes A and B form a pair, an object entering A leaves B moving in the same direction, and an object entering B leaves A moving in the same direction. The consequences can be unpleasant. Suppose wormhole A at $(0,0)$ and wormhole B at $(1,0)$ are paired, and Bessie the cow starts at $(1/2, 0)$ walking in the $+x$ direction. She enters B, comes out of A, enters B again, and repeats that forever, trapped in an infinite cycle.

John knows where every wormhole is, and he knows Bessie always walks in the $+x$ direction, but he does not remember where she is right now. Count the pairings of the wormholes for which Bessie could get trapped in an infinite cycle after starting from some unlucky point. Two pairings are different when at least one pair differs.

• The first line contains the number of wormholes, $N$.
• Each of the next $N$ lines contains two space-separated integers, the $x$ and $y$ coordinates of one wormhole. Both coordinates are integers between 0 and 1,000,000,000.

Print the number of pairings for which Bessie could get stuck in a cycle after starting from some point and walking in the $+x$ direction.

Take four wormholes at the corners of a square, placed at $(0,0)$, $(1,0)$, $(1,1)$, $(0,1)$ in that order and numbered 1 to 4. Pair 1 with 2 and 3 with 4, and Bessie gets stuck whenever she starts between $(0,0)$ and $(1,0)$ or between $(0,1)$ and $(1,1)$. Pair 1 with 3 and 2 with 4, and the same starting points trap her again. Only when 1 is paired with 4 and 2 with 3 can Bessie walk in the $+x$ direction from any point of the plane without cycling.