#P1556. 幸福的路

幸福的路

题目描述

每天,John 都要为了农场里 nn1n101 \leq n\leq 10) 头牛的健康和幸福四处奔波。

每头牛的位置可以描述为一个二维坐标,John 从坐标原点 (0,0)(0,0) 出发。为了使路径更有趣,John 决定只沿着平行于坐标轴的方向行走,这样只能沿着东西南北方向运动。而且只有到达某头牛的坐标后 John 才会改变行走的方向(当然,如果有必要,John 也会穿过某头牛的坐标而不改变行走的方向。)

如果 John 改变行走的方向,他会原地转 9090^\circ 或者 180180^\circ。John 的路径必须保证检查完所有牛后返回原点。

John 可以穿过某头牛的坐标而不改变方向任意次,请计算出有多少条路径满足 John 能检查完 nn 头牛,在每头牛的坐标处恰好改变一次方向。同一条路径从不同方向经过要计算两次。

输入格式

第一行,整数 nn

第二行到第 n+1n+1 行,第 i+1i+1 行是两个用空格隔开的整数 xxyy,表示第 ii 头牛的坐标(1000x,y1000-1000 \leq x,y \leq 1000)。

输出格式

一行一个整数,表示路径的量。如果没有满足要求则输出 00

4
0 1
2 1
2 0
2 -5
2