0 人解决，2 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。
1757. Fold-up Patterns
单点时限: 2.0 sec
内存限制: 256 MB
Fold-up patterns for solids like cubes or octahedrons can be found in many books on geometry, but without actually folding them it is hard to tell whether the constructions really work. In this problem, we will consider a special class of such patterns.
Note that even the second pattern above satisfies our definition of a closed surface, but the interior is not connected.
Two different squares may not occupy exactly the same position in space, though they may (and will for a closed surface) touch at edges and vertices. Make sure that the pattern does not interpenetrate itself through connected edges. Apart from that, do not worry about the process of folding, e.g. what edges are folded first or whether part of the structure is in the way for the rest.
输入格式
The input file consists of several test cases.
For each test case, the first line contains two integers n and e. These are the number n (1 <= n <= 200) of squares in the pattern and the number e (0 <= e <= 300) of edges. Squares are labelled by the integers 0 to n - 1. The following e lines describe one edge each using the four numbers s1; s2; p; f :
The two numbers s1 and s2 (with 0 <= s1 < s2 < n) of the squares that are joined by the edge.
The position p of the square s2 with respect to the square s1 in the pattern. Here p = 0;1;2;3 mean above, to the left, below, or to the right of s1, respectively (see sketch below).
The number f =0;1;2 tells you to fold along the edge either not at all, forward, or back, respectively (see sketch).
You can also assume that the pattern is connected and can be drawn in the plane without overlapping.
At the end of the input file, there will be a line containing two zeros (instead of n and e). Do not process that line.
输出格式
For each scenario print “Test case #k:”, where k is the number of the test case (starting from 1).
Then, on the same line, print either “not a closed surface” if the pattern does not form a closed surface or “closed surface, volume=” and the volume as an integer if it does.
样例
Input
6 5 0 2 2 1 1 2 3 1 2 3 3 1 2 4 2 1 4 5 2 1 5 4 0 2 2 1 1 2 3 1 2 3 3 1 2 4 2 1 0 0
Output
Test case #1: closed surface, volume=1 Test case #2: not a closed surface Hint:
题目标签