The Bulk

ID: 398

传统题

1000ms

256MiB

尝试: 3

已通过: 1

难度: 10

上传者:

Hydro

标签>

计算几何

离散化与扫描

Central Europe 2000

题目描述

ACM 使用了一种新的特殊技术来建造其收发站。这种技术被称为模块化长方体架构（Modular Cuboid Architecture，MCA），并已获得乐高公司的专利。收发站的所有部件都以单位块的形式运输，这些单位块是完全相同大小的立方体。这些立方体可以相互连接。MCA 是一种模块化架构，这意味着我们可以选择首选的收发站配置，并仅购买所需的组件。

立方体必须始终以“面对面”的方式连接，即一个立方体的整个侧面与另一个立方体的整个侧面相连。因此，一个立方体最多可以与其他六个单位块连接。由这些单位立方体组成的设备在通信技术中被称为Bulk。

有时，旧的、不再需要的 Bulk 会被废弃，放入存储区，并替换为新的 Bulk。最近发现 ACM 有许多这样的旧 Bulk，它们只是占用空间且不再需要。主管决定将所有此类 Bulk 拆解为单个单位块以节省空间。不幸的是，这些旧 Bulk 没有文档记录，没有人知道它们由多少单位块组成。你需要编写一个计算机程序，根据 Bulk 的描述计算其单位立方体的数量。

每个 Bulk 由其面（侧面）描述。一种特殊的基于 X 射线的机器能够定位 Bulk 在空间中的所有面，包括内部的面，因为 Bulk 可能是部分空心的（内部可能包含空的空间）。但任何 Bulk 必须是连通的（即不能分成两部分），并且由完整的单位立方体组成。

输入格式

输入的第一行是一个正整数 $T$ ，表示接下来要处理的 Bulk 数量。每个 Bulk 的描述以一行包含一个正整数 $F$ 开始，表示面的数量（ $6 \leq F \leq 250$ ）。然后是 $F$ 行，每行描述一个面。Bulk 的所有面总是被列出，顺序不限。任何面可能被分成多个独立的部分并像多个面一样描述。面不会重叠。每个面有一个内侧和一个外侧。没有面可以“部分内侧和部分外侧”。

每个面的描述占一行。行首是一个整数 $P$ ，表示确定该面的点数（ $4 \leq P \leq 200$ ）。然后是 $3 \times P$ 个数字，表示点的坐标。每个点由三个坐标 $X, Y, Z$ （ $0 \leq X, Y, Z \leq 1000$ ）描述，用空格分隔。点之间以及点与数字 $P$ 之间用两个空格分隔。这些额外的空格是为了使输入更易读。面可以通过按指定顺序连接点来构造，并将最后一个点与第一个点相连。

面总是由“单位正方形”组成，这意味着每条边要么沿 $X$ 轴、 $Y$ 轴或 $Z$ 轴方向。如果取任意两个相邻点 $(X1, Y1, Z1)$ 和 $(X2, Y2, Z2)$ ，那么这两个点总是恰好在一个坐标上不同。即要么 $X1 \neq X2$ ，要么 $Y1 \neq Y2$ ，要么 $Z1 \neq Z2$ ，其他两个坐标相同。每个面位于一个正交平面中，即所有点的一个坐标总是相同的。面的轮廓永远不会接触或交叉自身。

输出格式

对于每个测试用例，你的程序必须输出一行。该行必须包含句子 The bulk is composed of V units.，其中 $V$ 是 Bulk 的体积。

示例输入 1

2
12
4  10 10 10  10 10 20  10 20 20  10 20 10
4  20 10 10  20 10 20  20 20 20  20 20 10
4  10 10 10  10 10 20  20 10 20  20 10 10
4  10 20 10  10 20 20  20 20 20  20 20 10
4  10 10 10  10 20 10  20 20 10  20 10 10
5  10 10 20  10 20 20  20 20 20  20 15 20  20 10 20
4  14 14 14  14 14 16  14 16 16  14 16 14
4  16 14 14  16 14 16  16 16 16  16 16 14
4  14 14 14  14 14 16  16 14 16  16 14 14
4  14 16 14  14 16 16  16 16 16  16 16 14
4  14 14 14  14 16 14  16 16 14  16 14 14
4  14 14 16  14 16 16  16 16 16  16 14 16
12
4  20 20 30  20 30 30  30 30 30  30 20 30
4  10 10 10  10 40 10  40 40 10  40 10 10
6  10 10 20  20 10 20  20 30 20  30 30 20  30 40 20  10 40 20
6  20 10 20  20 20 20  30 20 20  30 40 20  40 40 20  40 10 20
4  10 10 10  40 10 10  40 10 20  10 10 20
4  10 40 10  40 40 10  40 40 20  10 40 20
4  20 20 20  30 20 20  30 20 30  20 20 30
4  20 30 20  30 30 20  30 30 30  20 30 30
4  10 10 10  10 40 10  10 40 20  10 10 20
4  40 10 10  40 40 10  40 40 20  40 10 20
4  20 20 20  20 30 20  20 30 30  20 20 30
4  30 20 20  30 30 20  30 30 30  30 20 30

示例输出 1

The bulk is composed of 992 units.
The bulk is composed of 10000 units.

来源