| 题目名称 | 1459. [USACO DEC13]虫洞 |
|---|---|
| 输入输出 | wormhole.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2013-12-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：23， 提交：51， 通过率：45.1% | ||||
 Youngsc |
100 | 0.000 s | 0.00 MiB | C++ |
 Dissolute丶Tokgo |
100 | 0.026 s | 0.29 MiB | C++ |
 Extreme°/极致 ° |
100 | 0.030 s | 0.30 MiB | C++ |
 黑夜<=>白天 |
100 | 0.032 s | 0.31 MiB | C++ |
 _Horizon |
100 | 0.033 s | 0.30 MiB | C++ |
 Aglove |
100 | 0.041 s | 0.31 MiB | C++ |
 cstdio |
100 | 0.044 s | 0.31 MiB | C++ |
 digital-T |
100 | 0.046 s | 0.32 MiB | C++ |
 coastline>> |
100 | 0.053 s | 0.30 MiB | C++ |
 夏尼玛 |
100 | 0.055 s | 0.32 MiB | C++ |
| 关于 虫洞 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
竟然一遍过了！尼玛幸福来的太突然……
看我debug | ||||
|
搜索连接状况，用“从每个洞开始走一次”的方法判断是否死循环
| ||||
啊吧啦吧啦吧【题目描述】
农夫约翰在周末进行高能物理实验的爱好适得其反，导致他的农场中有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<=N<=12,且为偶数）。
第2..1+N行：每行包含两个整数，描述（x，y），一个单一的虫洞坐标。每个坐标的范围是0..1000000000。
【输出格式】
行1：独特的虫洞配对的数目
她可以呆在一个循环周期中，在任意的出发点出发，在+X方向移动。
即：会使贝茜从某个起始点出发沿+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