BSP Ağacları
Bir səhnədə çox sayda obyekt göstərərkən, obyektlərin çəkilmə sırası çox önəmlidir. Ümumiyyətlə, obyekt ekrandan nə qədər uzaqdadırsa, o qədər tez çəkilməlidir ki, daha sonra yaxın olan obyektlər onların üstündə çəkilə bilsin. İki obyekt üst-üstə düşmürsə, çəkilmə sırası əhəmiyyət daşımır. İkili məkan-bölmə (BSP) ağacı obyektlərin sırasını müəyyənləşdirməyi sadələşdirməyə çalışan bir növ məlumat strukturdur. O, aşağıdakı kimi işləyir. Ekranın xy-müstəvisində, z-oxunun mərkəzində yerləşdiyini və z-oxunun ekrana baxan istifadəçidən uzağa doğru yönəldiyini fərz edək. (Bizim məqsədlərimiz üçün, istifadəçinin z-oxunda - ∞ yaxınlığında yerləşdiyini fərz edək.) Həmçinin fərz edirik ki, bütün obyektlər ekranın əks tərəfində yerləşir (z > 0). BSP ağacı y-oxuna paralel olan bir sıra müstəvilər yerləşdirilərək qurulur. İlk müstəvi məkanı iki bölgəyə ayırır: istifadəçini ehtiva edən bölgə və istifadəçini ehtiva etməyən bölgə. Məkanı bu iki bölgədən hansında yerləşdiyinə görə bütün obyektləri bölürük və müşahidə edirik ki, istifadəçini ehtiva edən bölgədəki bütün obyektlər digər bölgədəki bütün obyektlərdən sonra çəkilməlidir. BSP ağacı bu nöqtədə yalnız iki uşağı olan bir kök kimi görünə bilər, hər bir uşaq bir bölməni ehtiva edir. İndi ikinci bir müstəvi əlavə edə bilərik, bu məkanı yenidən alt bölmələrə ayırır. İlk müstəvidən olan iki bölmənin hər birini iki yerə bölürük, cəmi 4 bölmə olur və nəticədə BSP ağacı üç səviyyəyə malik olur, bölmələr yarpaqlarda yerləşir (qeyd edək ki, bu bölmələrin bəziləri bir neçə obyekt ehtiva edə bilər və bəziləri heç birini ehtiva etməyə bilər). Bu proses hər bir bölmədə ən çox bir obyekt olana qədər və ya əvvəlcədən müəyyən edilmiş müstəvi sayı istifadə olunana qədər davam etdirilir. Aşağıdakı diaqram 1, 2 və 3 müstəvidən istifadə nümunəsini göstərir (y-oxu boyunca aşağıya baxaraq). Sadəlik üçün fərz edirik ki, bütün obyektlər z-oxuna paraleldir, beləliklə BSP ağacını müəyyən etmək üçün yalnız bu 2-d təsviri ilə məşğul olmalıyıq.
Bölmələri düzgün şəkildə ayırdığınızı fərz edərək, BSP ağacının sadə bir keçidi səhnədəki obyektlərin göstərilməsi üçün uyğun bir sıra verəcəkdir. Yuxarıdakı nümunədə qeyd edin ki, bir düyün yalnız bir obyekt ehtiva etdikdə, əlavə müstəvilər əlavə edildikdə bölünməyə ehtiyac yoxdur.
Giriş verilənləri
Giriş bir neçə problem nümunəsindən ibarət olacaq. Hər bir nümunənin ilk sətri səhnədəki obyektlərin sayını göstərən müsbət tam ədəd n ≤ 20 olacaq. Növbəti n sətir bu obyektlərin təsvirini m x_1 z_1 x_2 z_2 .. x_m z_m formatında ehtiva edəcək, burada m obyektin təpə nöqtələrinin sayıdır və qalan dəyərlər obyektin xz-müstəvisi ilə kəsişməsinin təpə nöqtələridir. Bütün obyektlər 3 ilə 6 arasında təpə nöqtəsinə malik olacaq. Obyektlərin "A", "B", "C", ... olaraq təyin edildiyi sırada etiketləndiyi fərz edilir. Növbəti giriş faylında BSP ağacını yaratmaq üçün istifadə olunan müstəvilərin sayını göstərən müsbət tam ədəd p ≤ 10 olacaq. Son p giriş sətiri hər bir müstəvinin təsvirini x_1 z_1 x_2 z_2 formatında ehtiva edəcək, bu da müstəvinin və xz-müstəvisi ilə kəsişmə xəttindəki iki nöqtəni təmsil edir. Heç bir xəttin heç bir obyektlə (kənar və təpə nöqtələri daxil olmaqla) kəsişməyəcəyini və heç bir müstəvinin z-oxuna paralel olmadığını fərz edə bilərsiniz. Bütün koordinatlar tam ədədlər olacaq.
Çıxış verilənləri
Çıxış hər bir nümunə üçün obyektlərin göstərilməsi üçün BSP ağacı üçün uyğun olan sırada adlarını ehtiva edən bir sətirdən ibarət olacaq. Hər hansı bir bölmə iki və ya daha çox obyekt ehtiva etdikdə, obyektləri əlifba sırası ilə siyahıya almalısınız.