#Pusaco12marbronze2. 链接奶牛
链接奶牛
链接奶牛
题目描述
每天,农夫约翰在他的农场四处走动,检查他的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