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

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 секунда
Лимит использования памяти 64 MiB
Входные данные #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