logo AlgoBeat OnlineJudge
登录 注册

#200436. [USACO1.3] 虫洞 wormhole

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

样例输入 1

4
0 0
1 0
1 1
0 1

样例输出 1

2

数据范围与提示

数据范围

对于 的数据,
保证 为偶数。

样例解释

将虫洞编号为 ,然后通过将 匹配,如果 Bessie 从 之间的任意位置出发,她会陷入无限循环中。

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

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

题面翻译摘自 NOCOW