#P1444. [USACO1.3] 虫洞 wormhole

[USACO1.3] 虫洞 wormhole

题目描述

Farmer John 周末进行高能物理实验的结果却适得其反,导致 nn 个虫洞出现在农场上,农场是一个二维平面,没有两个虫洞处于同一位置。

根据他的计算,FJ 知道他的虫洞两两配对,形成 n2\dfrac{n}{2} 对配对。例如,如果 AABB 的虫洞连接成一对,进入虫洞 AA 的任何物体将从虫洞 BB 出去,方向不变;反之亦然。

然而这可能发生相当令人不快的后果。例如,假设有两个成对的虫洞 A(1,1)A(1,1)B(3,1)B(3,1),Bessie 从 (2,1)(2,1) 开始朝着 xx 正方向移动。Bessie 将进入虫洞 B(3,1)B(3,1),从 A(1,2)A(1,2) 出去,然后再次进入 BB,困在一个无限循环中!

FJ 知道他的农场里每个虫洞的确切位置。他知道 Bessie 总是向 xx 正方向走进来,虽然他不记得贝茜的当前位置。

请帮助 FJ 计算有多少种虫洞配对方案,使得存在一个位置,使得 Bessie 从该位置出发,会被困在一个无限循环中。

输入格式

第一行一个正整数 nn,表示虫洞数量。

接下来 nn 行,每行两个整数 x,yx,y,表示一个虫洞的坐标。

输出格式

输出一行一个整数表示答案。

4
0 0
1 0
1 1
0 1
2

提示

数据范围

对于 100%100\% 的数据,2n122\le n \le 120x,y1090 \le x,y \le 10^9
保证 nn 为偶数。

样例解释

将虫洞编号为 141 \sim 4,然后通过将 1,21,23,43,4 匹配,如果 Bessie 从 (0,0)(0,0)(1,0)(1,0) 之间的任意位置出发,她会陷入无限循环中。

相似的,在相同的起始点,如果配对是 1,31,32,42,4,贝茜也会陷入循环。(如果贝西从 33 进去,11 出来,她会走向 22 ,然后被传送到 44,最后又回到 33

仅有 1,41,42,32,3 的配对允许贝茜从任何二维平面上的点向 xx 正方向走,而不出现无限循环。

题面翻译摘自 NOCOW