P1556 [USACO12MAR] Happy Road (Connect the Cows B)

Every day, John bustles around to ensure the health and happiness of $n$ ($1 \leq n \leq 10$) cows. Each cow’s position is given by a 2D coordinate, and John starts at the origin $(0, 0)$. To make the route more interesting, John decides to move only along directions parallel to the coordinate axes, that is, only north, south, east, or west. Moreover, John changes direction only upon reaching the coordinate of some cow (of course, if necessary, John may also pass through a cow’s coordinate without changing direction). If John changes direction, he turns in place by $90^\circ$ or $180^\circ$. John’s path must visit all cows and then return to the origin. John may pass through any cow’s coordinate without changing direction any number of times. Please compute how many routes allow John to visit all $n$ cows, such that he changes direction exactly once at each cow’s coordinate. The same geometric path traversed in the opposite direction should be counted twice.

The first line contains an integer $n$, as described above. The next $n$ lines each contain two space-separated integers $x$ and $y$, where line $i+1$ gives the coordinates of the $i$-th cow ($-1000 \leq x, y \leq 1000$).

Output a single integer on one line, the number of valid routes (output `0` if there are no valid routes).

Translated by ChatGPT 5