#UT135. [USACO1.3.5] 虫洞 Wormholes
[USACO1.3.5] 虫洞 Wormholes
虫洞
农民约翰在周末进行高能物理实验的爱好适得其反,导致他的农场上出现了N个虫洞(2 <= N <= 12,N为偶数),每个虫洞位于他农场的2D地图上的一个独特点(x,y坐标均为整数)。
根据他的计算,农民约翰知道他的虫洞将形成N/2个连接对。例如,如果虫洞A和B作为一对连接,则任何进入虫洞A的物体都会从虫洞B以相同的方向退出,任何进入虫洞B的物体也会以相同的方向从虫洞A退出。这可能会产生相当糟糕的后果。
例如,假设有一对虫洞A位于(1,1),B位于(3,1),而且贝西奶牛从位置(2,1)开始朝+x方向移动。贝西将进入虫洞B(在(3,1)),从A(在(1,1))退出,然后再次进入B,如此反复,陷入无限循环!
| . . . .
| A > B . 贝西将先走向B,然后
+ . . . . A,然后再次穿越到B
农民约翰知道每个虫洞在他农场上的确切位置。他知道贝西奶牛总是朝+x方向走,尽管他不记得贝西当前的位置。
请帮助农民约翰计算虫洞的不同配对数量,以便贝西有可能在某个不幸的位置中被困在无限循环中。农民约翰不知道哪个虫洞与其他虫洞配对,因此请找出所有可能性。
程序名称:wormhole
输入格式:
- 第1行:虫洞的数量N。
- 第2行到第1+N行:每行包含两个用空格分隔的整数,描述一个虫洞的(x,y)坐标。每个坐标的范围为0..1,000,000,000。
示例输入(文件 wormhole.in):
4
0 0
1 0
1 1
0 1
输入详情:
有4个虫洞,形成一个正方形的四个角。
输出格式:
- 第1行:虫洞的不同配对数量,使得贝西在某个起始点朝+x方向行走时可能被困在循环中。
示例输出(文件 wormhole.out):
2
输出详情:
如果我们将虫洞编号为1..4(根据输入顺序),那么如果虫洞1与虫洞2配对,虫洞3与虫洞4配对,那么贝西可以在(0,0)和(1,0)之间或(0,1)和(1,1)之间的任何地方被困。
| . . . .
4 3 . . . 贝西将先走向B,然后
1-2-.-.-. A,然后再次穿越到B
同样,在相同的起始点下,如果配对为1-3和2-4(如果贝西进入虫洞#3并在虫洞#1退出,她随后走向虫洞#2,这将她送往虫洞#4,最后再次指向虫洞#3循环),也会使贝西被困。
只有配对1-4和2-3允许贝西朝+x方向走,从任何点在2D平面上行走而没有循环的危险。