1899: 拜访奶牛

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

每天,Farmer John 都会在他的农场四处走动,检查他的 N 头奶牛的健康状况。
每头奶牛的位置由二维平面中的一个点描述,Farmer John 从原点 (0,0) 开始。 
为了让他的路线更有趣,Farmer John 决定他将只沿着与坐标轴平行的方向行走——也就是说,只有东南西北。
此外,他只有在到达一头牛的位置时才改变他的行进方向(如果需要,他也可以选择不改变方向地穿过一头牛的位置)。 
当他改变行进方向时,他可能会转 90 度或 180 度。 
Farmer John 的路线必须在访问完他所有的奶牛后回到原点。
请计算如果 Farmer John 在每头奶牛的位置最多改变一次方向,有多少条不同的路线去拜访他的 N 头奶牛。 

输入格式

第 1 行:正整数 N,1 <= N <= 10。
第 2 行 - 第 N + 1 行:第 i + 1 行输入两个整数 x 和 y,表示第 i 头牛的位置,-1000 <= x, y <= 1000。

输出格式

输出一个整数表示答案。

输入样例 复制

4
0 1
2 1
2 0
2 -5

输出样例 复制

2

数据范围与提示

来源:USACO 2012.3