Joey发明了一种名为欧拉(为了纪念伟大的数学家欧拉)的画图机器。在Joey上小学时,他知道了欧拉是从一个著名的问题开始研究图论的。这个问题是在一张纸上一笔画出一个图形(笔尖不离开纸面),并且笔尖要回到起点。欧拉证明了当且仅当画出的平面图形具备以下两个属性,才能按照要求画出这种图形:① 图形是连通的;② 每个顶点度数为偶数。 Joey的欧拉机器也是这样工作的。机器中包含了一支与纸面接触的铅笔,机器的控制中心发出一系列指令指示铅笔如何画图。纸面可以看成是无限的二维平面,也就是说,不必担心笔尖会超出边界。
开始画图时,机器发出一条指令,格式为(X0, Y0),这意味着铅笔将移动到起点(X0, Y0)。接下来的每条指令的格式均为(X′, Y′),表示铅笔将从当前位置移动到新位置(X′, Y′),从而在纸面上画出一条线段。新位置与前面每条指令中的位置都不相同。最后,欧拉机器总是发出一条指令,将铅笔移动到起点(X0, Y0)。另外,欧拉机器画出来的线绝不会重叠,但有可能会相交。 当所有指令发布并执行后,在纸上已经画出一个完美的图形,由于笔尖没有离开纸面,画出来的图形可以看成是一个欧拉回路。试计算这个欧拉回路将平面分成了多少个区域。
输入
输入文件中至多包含25个测试数据。每个测试数据的第1行为整数N (N≥4),表示测试数据中指令的数目;接下来有N对整数,用空格隔开,表示每条指令中的位置,第1对整数为起点位置。假定每个测试数据中指令的数目不超过300,所有位置的坐标范围在(-300, 300)。N = 0表示输入结束。
输出
对每个测试数据,输出一行,格式为“Case x: There are w pieces.”,其中x为测试数据的序号,从1开始计起。样例输入所描述的两个例子如图9.9所示。
样例
| 标准输入 复制文本 |
5 0 0 0 1 1 1 1 0 0 0 7 1 1 1 5 2 1 2 5 5 1 3 5 1 1 0 |
| 标准输出 复制文本 |
Case 1: There are 2 pieces. Case 2: There are 5 pieces. |