Задачи
3D Blobs
3D Blobs
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 "\textbf{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 "\textbf{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 (\textbf{x}, \textbf{y}, \textbf{z}), (\textbf{x+1}, \textbf{y}, \textbf{z}), ..., (\textbf{x+1}, \textbf{y+1}, \textbf{z+1}). (\textbf{x}, \textbf{y}, \textbf{z}) is called the minimal vertex of a given cube, and is used to specify the cube.
The blobs specified by the Test Case \textbf{1} is shown below. Some vertexes are labeled:
\includegraphics{https://static.e-olymp.com/content/1c/1c1a430359296c965cc718c8682bc5693ff1ca15.jpg}
The example consists of 6 cubes that form \textbf{2} blobs. One blob consists of cubes (\textbf{1}, \textbf{1}, \textbf{1}), (\textbf{2}, \textbf{1}, \textbf{1}), (\textbf{2}, \textbf{2}, \textbf{1}) (obscured) and (\textbf{2}, \textbf{2}, \textbf{2}); it has a surface area of \textbf{18}. The other blob consists of cubes (\textbf{1}, \textbf{3}, \textbf{1}) and (\textbf{1}, \textbf{3}, \textbf{2}); it has a surface area of \textbf{10}. Therefore the total surface area is \textbf{28}.
\InputFile
The first input line contains the number of test cases \textbf{N}, \textbf{1} ≤ \textbf{N} ≤ \textbf{50}.
Each test case begins with an integer \textbf{n}, on a single line. \textbf{n} lines follow, each containing integers \textbf{x_i}, \textbf{y_i}, and \textbf{z_i} (for \textbf{1} ≤ \textbf{i} ≤ \textbf{n}) separated by space.
\begin{itemize}
\item \textbf{n} is the number of cubes, and satisfies \textbf{1} ≤ \textbf{n} ≤ \textbf{100}.
\item (\textbf{x_i}, \textbf{y_i}, \textbf{z_i}) is the minimal vertex of cube \textbf{i}, and satisfies \textbf{1} ≤ \textbf{x_i}, \textbf{y_i}, \textbf{z_i} ≤ \textbf{1000000}.
\item All cubes are distinct (within each test case).
\end{itemize}
\OutputFile
For each test case, print the sentence "\textbf{m blob(s) with area A}" on a single line, where \textbf{m} is the number of blobs, and \textbf{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