eolymp
bolt
Try our new interface for solving problems

3D Blobs

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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.

Giriş verilənləri

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).

Çıxış verilənləri

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.

Nümunə

Giriş verilənləri #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
Çıxış verilənləri #1
2 blob(s) with area 28
1 blob(s) with area 24
2 blob(s) with area 12
Mənbə University of Toronto 2010 ACM Tryout: Saturday, October 2, 2010