该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

每天农夫约翰都会去巡视农场，检查他的 N 头奶牛的健康状况。

每头奶牛的位置由二维平面中的一个点描述，而约翰从原点 (0,0) 出发。

所有奶牛的位置互不相同，且都不在原点。

为了使自己的路线更有趣，农夫约翰决定只沿平行于坐标轴的方向行走，即只能向北，向南，向东或向西行走。

此外，他只有在到达奶牛的位置时才能改变行进方向（如果需要，他也可以选择通过奶牛的位置而不改变方向）。

在他改变方向时，可以选择转向 90或 180度。

约翰的行进路线必须满足在他访问完所有奶牛后能够回到原点。

如果他在每头奶牛的位置处恰好转向一次，请计算出约翰访问他的 N头奶牛可以采取的不同路线的数量。

允许他在不改变方向的情况下通过任意奶牛的位置任意次数。

同一几何路线正向走和反向走算作两条不同的路线。

输入格式

第一行包含整数 N。

接下来 N行，每行包含两个整数 (x,y)，表示一个奶牛的位置坐标。

输出格式

输出不同路线的数量。

如果不存在有效路线，则输出 0。

数据范围

• 1 ≤ N ≤ 10
• -1000 ≤ x, y ≤ 1000
• 所有奶牛位置互不相同且不在原点

输入样例

4
0 1
2 1
2 0
2 -5

输出样例

2

样例解释

存在两条有效路线：

1. 路线1→2→4→3
2. 路线3→4→2→1

解题提示

1. 考虑使用状态压缩动态规划
2. 需要记录当前状态、最后访问的奶牛和移动方向
3. 注意处理转向约束条件
4. 最终必须返回原点

时间/空间限制

• 时间限制：1秒
• 空间限制：64MB

题目来源

USACO 2012 March Contest Bronze Division