TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1210
  • 题目
  • P1210连接奶牛
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    每一天,FJ都要在农场里四处走动,去观察他的N(1 <= N <= 10)头奶牛。每头奶牛的位置是在二维平面上的一个点。FJ起始位置在坐标原点(0,0)。
    FJ行走的路线一定是平行于坐标轴的,即只走东、南、西、北四个方向。他可以在走到一头牛的位置时,绕过去而不观察它,这样,FJ就可以选择去观察同一方向上的另一头牛。而只要决定观察它,就必须在随后改变行走方向。
    他在转向时,可以作90度或者180度的转向。他在观察过所有的N头牛之后,必须返回原点。
    请计算出FJ有多少种不同的行走方法,他在观察某一头牛后只能改变一次方向,也就是说,他只能对某头牛观察一次。但他可以绕过某头牛的位置任意多次。
    几何形状相同的路线正向行走和反向行走被认为是两条路线。

    输入格式

    第1行: 1个整数N(1 <= N <= 10).
    第2..1+N行: 第i行有2个空格分开的整数x, y表示第i头年的坐标。-1000<=x,y<=1000

    输出格式

    第1行: 1个整数,表示不同的行走方法数。如果找不到合法的路线,方法数为0.

    样例输入

    4
    0 1
    2 1
    2 0
    2 -5

    样例输出

    2

    提示

    FJ可以按照1-2-4-3 或者 3-4-2-1 的顺序行走。


    来源  USACO MAR12 铜组