Solution Notes: We solve this problem by "brute force". Since we need to change direction exactly once at each cow (many students seem to have overlooked this condition!) it suffices to enumerate all possible N! permutations of cows. For each permutation, we see if it gives us a valid ordering of the direction change events at our N cows (i.e., is each successive cow horizontally or vertically located relative to the previous cow on the permutation, and does the direction to this cow represent a change in direction from our previous direction?). In C++, one can use the next_permutation() function to generate all N! permutations very easily; since not all competitors might know about this function, the straight C code below shows how to enumeration through permutations using recursion.

``````
#include <stdio.h>
#define SWAP(a,b) tmp=a; a=b; b=tmp

int N, X[12], Y[12];

int get_dir(int x1, int y1, int x2, int y2)
{
if (x1!=x2 && y1!=y2) return -1;  /* No direction */
if (x1==x2 && y1<y2) return 0;  /* p2 north of p1 */
if (x1==x2 && y1>y2) return 1;  /* p2 south of p1 */
if (y1==y2 && x1<x2) return 2;  /* p2 east of p1 */
if (y1==y2 && x1>x2) return 3;  /* p2 west of p1 */
}

/* Check a permutation... */
int check(int *p)
{
int i;
for (i=1; i<=N+1; i++)
if (get_dir(X[p[i]], Y[p[i]], X[p[i-1]], Y[p[i-1]])==-1) return 0;
for (i=1; i<=N; i++)
if (get_dir(X[p[i]], Y[p[i]], X[p[i-1]], Y[p[i-1]]) ==
get_dir(X[p[i+1]], Y[p[i+1]], X[p[i]], Y[p[i]])) return 0;
return 1;
}

/* Generate and check all permutations... */
int perm(int n, int *so_far, int *remaining)
{
int i, tmp, total=0;
if (n==N) return check(so_far);
for (i=0; i<N-n; i++) {
so_far[n+1] = remaining[i];
SWAP(remaining[i], remaining[N-n-1]);
total += perm(n+1, so_far, remaining);
SWAP(remaining[i], remaining[N-n-1]);
}
}

int main(void)
{
int P[12] = {0}, D[10] = {1,2,3,4,5,6,7,8,9,10}, i;

freopen ("connect.in", "r", stdin);
freopen ("connect.out", "w", stdout);

scanf ("%d", &N);
for (i=1; i<=N; i++)
scanf ("%d %d", &X[i], &Y[i]);

printf ("%d\n", perm (0,P,D));

return 0;
}
``````