OI题库

【题目描述】

农夫约翰在周末进行高能物理实验的爱好适得其反，导致他的农场中有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