shunfurh 于 2017.09.14 16:44 提问

Overlapping Objects

There are many objects in space with possible overlapping with each other. The space may have arbitary dimension. A one-dimension object is a segment; A two-dimension object is a rectangle; A three-dimension object is a cube, etc.
Given a set of such objects, you will have to calculate the overlapping region of them.

Input

Input contains multiple tests. Each test starts with two integers, m (0 < m <= 10, the dimension of the case) and n (0 < n <= 3, the number of objects). A test with m = 0 and n = 0 indicates the end of input. This test is not to be processed.

The following n lines contain 2m integers each, in the form x1 x2 (-10000 <= x1 < x2 <= 10000) y1 y2 ...

Output

For each case output several lines in the form: num area, where num is the number of objects and area is the total length, area, volumn, etc. of overlapping region of num objects. The entries are sorted in ascending order and entries with area of 0 is omitted.

Sample Input

1 1
0 1
2 2
0 2 0 2
1 3 1 3
0 0

Sample Output

1 1
1 6
2 1

1个回答

devmiao      2017.09.30 08:32