#Pusaco12marbronze2. 链接奶牛

    ID: 675 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>bronzeusaco赛制:OI来源:wyfoj http://127.0.0.1组合数学枚举

链接奶牛

链接奶牛

题目描述

每天,农夫约翰在他的农场四处走动,检查他的N(1 <= N <= 10)奶牛的健康状况和健康状况。每个母牛的位置由2D平面中的一个点描述,而农夫约翰从原点开始(0,0)。为了使他的路线更有趣,农夫约翰决定他只会沿着与坐标轴平行的方向行走 - 也就是说,只有北,南,东或西。此外,当他到达母牛的位置时,他只改变他的行进方向(如果需要,他也可以选择通过母牛的位置而不改变方向)。当他改变他的旅行方向时,他可以做90度或180度转弯。农夫约翰的路线必须在他访问了所有的奶牛后将他带回原点。如果他在每头奶牛的位置改变方向一次,请计算农夫约翰可以用来访问他的N头奶牛的不同路线的数量。允许他在不改变方向任意次数的情况下穿过母牛的位置。前向与后向相同的几何路线计为两条不同的路线。

(注意通过母牛的位置而不改变方向,不算碰到奶牛,通过母牛的位置改变他的旅行方向才算访问了奶牛)

输入格式

第1行:整数N. 第2..1 + N行:第i+1行包含第i个点的x和y坐标(以空格分隔)(每个值都在范围内) (-1000 ... 1000)

输出格式

1行:农夫约翰可以采用的不同路线的数量(如果没有可以访问所有奶牛的路线,则可以为零)

数据范围

(原站未提供,导入后需人工补齐)

样例

4
0 1
2 1
2 0
2 -5
2

有两条可以访问所有奶牛返回原点的路径
1-2-4-3 和 3-4-2-1