SP7 BULK - The Bulk!

题目描述

ACM 使用了一种构建其收发信站的新型特殊技术。该技术称为模块化长方体结构(Modular Cuboid Architecture,简称 MCA),并受乐高公司专利保护。所有收发信机的部件均以单元模块形式运输,这些模块恰好都是尺寸完全相同的立方体。立方体模块可以相互连接。MCA 是一种模块化结构,意味着我们可以选择所需的收发信机配置,只购买所需的组件。 立方体模块必须始终“面对面”连接,即一个立方体的整个面与另一个立方体的整个面相连接。因此,每个立方体最多可与六个其他单元相连。由单元立方体组成的最终设备在通信技术领域俗称为 Bulk。 有时,一些旧的且不再需要的 Bulk 会被废弃,存放到仓库,并由新的 Bulk 取代。最近发现 ACM 有许多此类仅占用空间且不再需要的旧 Bulk。主管决定将所有这类 Bulk 拆解为单个模块,以节省空间。不幸的是,这些旧 Bulk 没有任何文档记录,也无人知道组成它们的模块数量。你需要编写一个计算机程序,根据 Bulk 的描述计算单元立方体的数量。 每个 Bulk 由其表面(面)来描述。构造了一台基于 X 射线的专用设备,能够定位 Bulk 的所有表面,包括内部表面,因为 Bulk 可能部分中空(内部可能包含空腔)。但任何 Bulk 必须是连通的(即不能分成两部分),且由完整的单元立方体组成。

输入格式

输入的第一行是一个正整数 $T$(约等于 $1000$),表示接下来要处理的 Bulk 数量。每个 Bulk 的描述以一行正整数 $F$ 开头,$6 \le F \le 250$,表示表面数量。随后有 $F$ 行,每行描述一个表面。Bulk 的所有表面都会被列出,顺序任意。每个表面可能被划分成若干独立部分,并按多个表面来描述。各表面之间不会重叠。每个表面都有内侧和外侧,任何一侧不会“部分为内侧而部分为外侧”。 每个表面由一行描述。该行以整数 $P$ 开头,表示确定该表面的点的数量,$4 \le P \le 200$。随后有 $3 \times P$ 个数字,表示这些点的坐标。每个点由三个坐标 $X$、$Y$、$Z$($0 \le X, Y, Z \le 1000$)组成,坐标之间以空格分隔。各点与相邻点之间、以及与前面的 $P$ 之间以两个空格分隔,以提高可读性。该表面可通过依次连接给定点,以及将最后一点与第一点连接而形成。 表面总是由“单位正方形”组成,即每条边沿 $X$、$Y$ 或 $Z$ 轴方向延伸。任取相邻两点 $(X _ 1, Y _ 1, Z _ 1)$ 和 $(X _ 2, Y _ 2, Z _ 2)$,它们在且仅在一个坐标上不同,即要么 $X _ 1 \ne X _ 2$,要么 $Y _ 1 \ne Y _ 2$,要么 $Z _ 1 \ne Z _ 2$,其余两个坐标相同。每个表面都位于某个正交平面上,即该平面上所有点的某一坐标恒相同。表面轮廓不会自相接触或自相交叉。

输出格式

对于每个测试用例,你的程序必须输出一行,格式为 $\texttt{The bulk is composed of }V\texttt{ units.}$,其中 $V$ 为该 Bulk 的体积(单元立方体数量)。

说明/提示

**输入 / 输出数据量大,请在某些语言中谨慎处理。**