BSP деревья
При отрисовке сцены с несколькими объектами на экране важно учитывать порядок их отображения. Обычно объекты, находящиеся дальше от экрана, должны быть нарисованы первыми, чтобы более близкие объекты могли быть нарисованы поверх них. Если объекты не перекрываются, порядок отрисовки не имеет значения. Дерево бинарного разбиения пространства (BSP) — это структура данных, которая помогает определить порядок отрисовки объектов. Оно работает следующим образом. Предположим, что экран находится в xy-плоскости, центрированной на z-оси, и что z-ось направлена от пользователя, смотрящего на экран. (Предположим, что пользователь находится около -∞ на z-оси.) Также предположим, что все объекты находятся на противоположной стороне экрана (z > 0). Дерево BSP строится путем размещения серии плоскостей, параллельных y-оси. Первая плоскость делит пространство на две области: область, содержащую зрителя, и область, не содержащую зрителя. Мы распределяем все объекты в зависимости от того, в какой из этих областей они находятся, и замечаем, что все объекты в области, содержащей зрителя, должны быть нарисованы после объектов в другой области. На этом этапе дерево BSP можно представить как корень с двумя дочерними узлами, каждый из которых содержит одну из частей. Затем добавляется вторая плоскость, которая снова делит пространство. Мы делим каждую из двух частей от первой плоскости на две, получая в итоге 4 части, и результирующее дерево BSP теперь имеет три уровня, с частями в листьях (заметьте, что некоторые из этих частей могут содержать несколько объектов, а некоторые могут не содержать ни одного). Этот процесс продолжается до тех пор, пока в каждой части не останется не более одного объекта или пока не будет использовано некоторое предопределенное количество плоскостей. Диаграмма ниже демонстрирует пример использования 1, 2 и 3 плоскостей (смотрим вниз вдоль y-оси). Для простоты мы предполагаем, что все объекты лежат параллельно z-оси, поэтому нам нужно только работать с этим 2-d изображением для определения дерева BSP.
Предполагая, что вы правильно разделили части, простое прохождение по дереву BSP даст вам правильный порядок, в котором следует отрисовывать объекты в сцене. Обратите внимание на приведенный выше пример: как только узел содержит только один объект, его не нужно делить, когда добавляются дополнительные плоскости.
Входные данные
Входные данные состоят из нескольких экземпляров задачи. Первая строка каждого экземпляра содержит положительное целое число n ≤ 20, указывающее количество объектов в сцене. Следующие n строк содержат описание этих объектов в формате m x_1 z_1 x_2 z_2 .. x_m z_m, где m — количество вершин в объекте, а оставшиеся значения — это координаты вершин пересечения объекта с xz-плоскостью. Все объекты имеют от 3 до 6 вершин. Предполагается, что объекты обозначены "A", "B", "C", ... в порядке их определения. Далее во входном файле будет положительное целое число p ≤ 10, указывающее количество плоскостей, использованных для создания дерева BSP. Последние p строк ввода содержат описание каждой плоскости в формате x_1 z_1 x_2 z_2, представляющем две точки на линии пересечения плоскости и xz-плоскости. Вы можете предположить, что ни одна линия не пересечет ни один объект (включая ребра и вершины) и что ни одна плоскость не параллельна z-оси. Все координаты будут целыми числами.
Выходные данные
Вывод должен состоять из одной строки для каждого экземпляра, содержащей имена объектов в порядке, в котором они должны быть отрисованы для указанного дерева BSP. Если какая-то часть содержит два или более объектов, перечислите объекты в алфавитном порядке.