eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

3D Blobs

3D Blobs

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

You are given a collection of unit cubes whose vertex coordinates are integers. Two cubes with a shared face are glued together. A connected mass of cubes forms a "blob". Your task is to count the number of blobs and find the total surface area of all blobs.

Note: A blob may have internal "bubbles". Its total surface area includes internal wall area of bubbles, as well as area contribution from trapped blobs inside bubbles.

Each unit cube has vertex coordinates (x, y, z), (x+1, y, z), ..., (x+1, y+1, z+1). (x, y, z) is called the minimal vertex of a given cube, and is used to specify the cube.

The blobs specified by the Test Case 1 is shown below. Some vertexes are labeled:

The example consists of 6 cubes that form 2 blobs. One blob consists of cubes (1, 1, 1), (2, 1, 1), (2, 2, 1) (obscured) and (2, 2, 2); it has a surface area of 18. The other blob consists of cubes (1, 3, 1) and (1, 3, 2); it has a surface area of 10. Therefore the total surface area is 28.

Вхідні дані

The first input line contains the number of test cases N, 1N50.

Each test case begins with an integer n, on a single line. n lines follow, each containing integers x_i, y_i, and z_i (for 1in) separated by space.

  • n is the number of cubes, and satisfies 1n100.

  • (x_i, y_i, z_i) is the minimal vertex of cube i, and satisfies 1x_i, y_i, z_i1000000.

  • All cubes are distinct (within each test case).

Вихідні дані

For each test case, print the sentence "m blob(s) with area A" on a single line, where m is the number of blobs, and A is the total surface area of blobs.

Приклад

Вхідні дані #1
3
6
1 1 1
2 1 1
2 2 1
2 2 2
1 3 1
1 3 2
8
1 1 1
1 2 2
2 1 2
2 2 1
1 1 2
1 2 1
2 1 1
2 2 2
2
1 1 1
1000000 1000000 1000000
Вихідні дані #1
2 blob(s) with area 28
1 blob(s) with area 24
2 blob(s) with area 12
Джерело University of Toronto 2010 ACM Tryout: Saturday, October 2, 2010