#P1444. [USACO1.3] 虫洞 wormhole
[USACO1.3] 虫洞 wormhole
题目描述
Farmer John 周末进行高能物理实验的结果却适得其反,导致 个虫洞出现在农场上,农场是一个二维平面,没有两个虫洞处于同一位置。
根据他的计算,FJ 知道他的虫洞两两配对,形成 对配对。例如,如果 和 的虫洞连接成一对,进入虫洞 的任何物体将从虫洞 出去,方向不变;反之亦然。
然而这可能发生相当令人不快的后果。例如,假设有两个成对的虫洞 和 ,Bessie 从 开始朝着 正方向移动。Bessie 将进入虫洞 ,从 出去,然后再次进入 ,困在一个无限循环中!
FJ 知道他的农场里每个虫洞的确切位置。他知道 Bessie 总是向 正方向走进来,虽然他不记得贝茜的当前位置。
请帮助 FJ 计算有多少种虫洞配对方案,使得存在一个位置,使得 Bessie 从该位置出发,会被困在一个无限循环中。
输入格式
第一行一个正整数 ,表示虫洞数量。
接下来 行,每行两个整数 ,表示一个虫洞的坐标。
输出格式
输出一行一个整数表示答案。
4
0 0
1 0
1 1
0 1
2
提示
数据范围
对于 的数据,,。
保证 为偶数。
样例解释
将虫洞编号为 ,然后通过将 和 匹配,如果 Bessie 从 到 之间的任意位置出发,她会陷入无限循环中。
相似的,在相同的起始点,如果配对是 和 ,贝茜也会陷入循环。(如果贝西从 进去, 出来,她会走向 ,然后被传送到 ,最后又回到 )
仅有 和 的配对允许贝茜从任何二维平面上的点向 正方向走,而不出现无限循环。
题面翻译摘自 NOCOW