Дерева 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-дерева. У випадку, коли деякий розділ містить два або більше об'єктів, ви повинні перерахувати об'єкти в алфавітному порядку.