BSP 트리

여러 물체가 있는 장면을 화면에 그릴 때, 물체를 그리는 순서는 매우 중요하다. 일반적으로 화면에서 더 멀리 있는 물체를 먼저 그려야, 나중에 그리는 가까운 물체가 그 위에 겹쳐 보이게 된다. 두 물체가 서로 겹치지 않는다면 그리는 순서는 상관없다.

이진 공간 분할(BSP, binary space-partitioning) 트리는 이러한 순서를 정하는 데 도움을 주는 자료구조이다. 화면은 $z$축을 중심으로 하는 xy-평면 위에 있고, $z$축은 화면을 보는 사람의 반대 방향을 가리킨다고 하자. 관찰자는 $z$축의 $-\infty$ 근처에 있으며, 모든 물체는 화면 반대편, 즉 $z > 0$ 영역에 놓여 있다.

BSP 트리는 $y$축과 평행한 평면들을 차례로 삽입하여 만든다. 첫 번째 평면은 공간을 두 영역으로 나눈다. 관찰자가 있는 영역과 관찰자가 없는 영역이다. 모든 물체를 자신이 속한 영역으로 분류하는데, 관찰자가 있는 영역의 물체들은 반드시 다른 영역의 물체들보다 나중에 그려야 한다. 이 시점에서 BSP 트리는 두 영역을 각각 자식으로 갖는 루트가 된다.

두 번째 평면은 공간을 다시 나누어, 앞의 두 영역을 각각 둘로 쪼개 총 네 개의 영역을 만든다. 이제 트리는 세 단계가 되고 각 영역은 잎(leaf)에 놓인다(한 영역에 여러 물체가 있을 수도, 하나도 없을 수도 있다). 이 과정은 모든 영역이 물체를 최대 한 개만 가질 때까지, 또는 미리 정해진 개수의 평면을 모두 사용할 때까지 반복한다. 한 영역에 물체가 하나만 남으면, 이후에 평면을 더 추가하더라도 그 영역은 더 나누지 않는다.

모든 물체는 $z$축과 평행하므로, xz-평면으로 투영한 모습($y$축 방향에서 내려다본 모습)만 다루면 된다. 아래 그림은 평면을 1개, 2개, 3개 사용했을 때의 모습을 보여준다.

이렇게 완성한 BSP 트리를 단순히 순회하면 물체를 그릴 올바른 순서를 얻을 수 있다.

입력은 하나의 장면을 설명한다.

• 첫째 줄에는 물체의 개수 $n$ ($1 \le n \le 20$)이 주어진다.
• 다음 $n$개의 줄에는 각 물체가 m x1 z1 x2 z2 ... xm zm 형식으로 주어진다. 여기서 $m$ ($3 \le m \le 6$)은 꼭짓점의 개수이고, 각 $(x_i, z_i)$는 물체를 xz-평면에서 자른 단면의 꼭짓점이다. 물체는 주어진 순서대로 A, B, C, ... 로 이름 붙인다.
• 그다음 줄에는 평면의 개수 $p$ ($1 \le p \le 10$)가 주어진다.
• 다음 $p$개의 줄에는 각 평면이 xz-평면과 만나는 직선 위의 두 점이 x1 z1 x2 z2 형식으로 주어진다.

어떤 평면의 직선도 물체(모서리와 꼭짓점 포함)와 만나지 않으며, $z$축과 평행한 평면은 없다. 모든 좌표는 정수이다.

주어진 BSP 트리에 따라 물체를 그려야 하는 순서대로 물체의 이름을 한 줄에 출력한다. 한 영역에 물체가 둘 이상 있으면, 그 물체들은 알파벳 순서로 나열한다.