#P1645. BSP树
ID: 646
远端评测题
1000ms
10MiB
Hydro
标签>

描述

将多个物体渲染到屏幕上时，物体的绘制顺序非常重要。通常，物体离屏幕越远，应越早绘制，以便后续较近的物体可以绘制在其上方。若两个物体不重叠，绘制顺序无关紧要。**二叉空间分割树（BSP树）**是一种简化物体绘制顺序确定的数据结构，其工作原理如下：

假设屏幕位于以z轴为中心的xy平面，z轴正方向远离看向屏幕的用户（假设用户位于z轴负无穷附近），所有物体位于屏幕另一侧（z > 0）。BSP树通过放置一系列平行于y轴的平面构建：

1. 第一平面将空间分为两部分：包含观察者的区域和不包含观察者的区域。所有物体按所在区域划分，包含观察者区域的物体应在另一区域物体之后绘制。此时BSP树为根节点，两个子节点分别对应两个分区。
2. 后续平面进一步分割空间。例如，第二平面将第一平面的两个分区各分为两部分，形成4个分区，BSP树变为3层，叶子节点为分区（部分分区可能包含多个物体或无物体）。
3. 重复此过程，直到每个分区最多包含一个物体，或达到预设平面数量。

为简化问题，假设所有物体平行于z轴，只需处理xz平面的二维图像即可构建BSP树。下图展示了使用1、2、3个平面的示例（沿y轴俯视）：

假设分区正确，简单遍历BSP树即可得到场景物体的绘制顺序。注意，若节点仅包含一个物体，后续添加平面时无需再分割该节点。

输入

输入包含一个测试用例：

1. 首行是正整数$n \leq 20$，表示场景中的物体数量。
2. 接下来$n$行描述物体，格式为m x1 z1 x2 z2 ... xm zm，其中$m$是物体的顶点数（3到6个），后续值为物体与xz平面交线的顶点坐标。物体按定义顺序标记为"A"、"B"、"C"…
3. 接下来是正整数$p \leq 10$，表示构建BSP树使用的平面数量。
4. 最后$p$行描述每个平面，格式为x1 z1 x2 z2，表示平面与xz平面交线的两个点。保证平面不与任何物体（包括边和顶点）相交，且不平行于z轴，所有坐标为整数。

输出

输出一行，按BSP树确定的绘制顺序列出物体名称。若分区包含多个物体，按字母顺序排列。

输入数据 1

10  
3 65 5 66 5 65 6  
3 65 123 66 123 65 124  
3 122 176 123 176 122 177  
3 56 23 57 23 56 24  
3 11 49 12 49 11 50  
3 167 111 168 111 167 112  
3 57 123 58 123 57 124  
3 130 6 131 6 130 7  
3 100 85 101 85 100 86  
3 11 28 12 28 11 29  
10  
159 165 -131 -177  
-153 -192 -197 158  
-77 -86 -98 30  
-177 59 146 63  
192 -117 92 43  
121 -67 -62 -134  
41 -81 130 196  
95 -185 -89 154  
-163 -179 93 175  
113 41 -92 -28  

输出数据 1

BCGEJFIHDA  

来源

2000年北美中东部地区赛