[USACO DEC13]虫洞

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file wormhole.in Output file wormhole.out

【题目描述】

农夫约翰在周末进行高能物理实验的爱好适得其反,导致他的农场中有N个虫洞(2 <= n <= 12),每一个位于在二维地图的不同点。根据他的计算,农民约翰知道他的虫洞有N/2个连接对。

例如,如果A和B是连接虫洞的连接对,那么任何进入虫洞A的物体将从虫洞B退出,任何物体进入虫洞B将同样从虫洞A退出。这可以有相当令人不快的后果。例如,假设有两个配对,虫洞在A(0,0)和B(1,0),而贝茜奶牛从位置(1/2,0)在+X方向移动。她将进入虫洞B,从虫洞A退出,然后再进入B,等等,被困在一个无限循环周期中!

农民约翰知道在他的农场里每一个虫洞的确切位置。他还知道贝茜奶牛总是走在+X方向,但是他不记得贝茜奶牛在哪里,即她现在的位置。请帮助农民约翰计算不同的虫洞配对的数目,满足如果她从一个倒霉的位置开始,她可能会被困在一个无限循环中。


【输入格式】


第1行:虫洞的数量,N。

第2..1+N行:每行包含两个整数,描述(x,y),一个单一的虫洞坐标。每个坐标的范围是0..1000000000。


【输出格式】


行1:独特的虫洞配对的数目

她可以呆在一个循环周期中,在任意的出发点出发,在+X方向移动。


【样例输入】

4
0 0
1 0
1 1
0 1

【样例输出】

2

【提示】



输入详细信息:

有4个虫洞,形成一个正方形的角部。


 输出的细节:


    我们来数一数1..4的虫洞,如果有虫洞对是1-2和3-4,她能从(0,0)和(1,0)或(0,1)和(1,1)开始,贝茜也可能呆在一个循环周期中。同样的,具有相同的出发点,如果有虫洞对1-3和2-4,贝茜也可能呆在一个循环周期中。

    仅当如果有虫洞对1-4和2-3允许贝西走在+X方向,则没有循环的危险。


【来源】


USACO Dec 13 Bronze

data from cstdio