Xilasetmə Mayakı#6044
Han Solo köhnə və bir o qədər də xoşbəxt olmayan kreditorlarından yayınmağa çalışarkən, Millennium Falcon-u buzlu Hoth planetinə çırpıb. İndi isə o, bir növ fövqəladə siqnal işlətməlidir ki, dostu Wookiee bir tüklü-buz parçasına dönmədən onun yanına kömək gəlsin. Ona kömək edə bilərsən?
Han, çox parlaq bir lazeri xilas edə bilib, hansı ki, işığı işıq illəri uzaqlıqdan görünə bilər və düşündü ki, bu yaxşı bir siqnal olar. Pis tərəfi odur ki, əgər o, lazeri sadəcə düz yuxarı səmağa işıqlandırsa, yalnız minimal ehtimal var ki, kimsə təsadüfən həmin işıq yolunda olub onu görə bilər. Bu arada, Chewbacca yaxınlıqdakı bir mağarada tapdığı çox parlaq, çoxüzlü kristallarla oynayırdı. Sonra, qəfil bir ilham anında, Han başa düşdü ki, o, lazer işığını kristala yönəldib, həmin kristalın səthlərini işıqlandıranda, işıq göyə bir çox istiqamətdə əks oluna bilər və beləliklə, qəza mayakı düzəldə bilər!
Şəkil 1: Hanın qəza mayakının sadələşdirilmiş, ikiölçülü illüstrasiyası.
Yeganə problem qalır: işığı əks etdirən kristal olaraq hansını seçmək lazımdır? Hər bir əks etdirici kristal səthi yalnız bərabəryanlı üçbucaqlardan ibarət olan qabarıq polihedral formadadır və mayaka istənilən oriyentasiyada yerləşdirilə bilər. Əlbəttə, ən yaxşı seçim işıq şüasını (bir istiqamətdən gələn paralel işıq şüalarından ibarət) eyni zamanda ən çox sayda istiqamətə əks etdirə bilən kristaldır. Başqa sözlə, kristalın əks etdirmə qabiliyyətini istənilən bir baxış istiqamətindən görünən səthlərin sayı kimi təsəvvür edə bilərsən, çünki eyni anda lazer şüasını həmin səthlər tuta bilər. Hər bir kristalın geometrik təsvirini nəzərə alaraq, kristalın lazeri ən çox istiqamətə əks etdirə biləcəyi maksimum səthin sayını hesablaya bilərsən?
Girişdə Chewbaccanın kolleksiyasındakı kristalların hər birinin geometrik təsviri verilir. Hər kristalın təsviri bir tam ədəd (4 \leq n \leq 2000) — kristalın səthlərinin sayı olan bir sətrdən, daha sonra isə sətrin hər birində bir səthin təsvirindən ibarətdir. Hər səthin təsviri tam ədəddən ibarətdir: x_1\ y_1\ z_1\ x_2\ y_2\ z_2\ x_3\ y_3\ z_3, burada (x_1, y_1, z_1), (x_2, y_2, z_2) və (x_3, y_3, z_3) nöqtələri sırasıyla səthin üç verteksi olub, saatın əksinə (sağ əl qaydasına uyğun) xarici tərəfdən baxdıqda düzgün ardıcıllıqla verilib. Bütün koordinatlar -2000 \leq x_i, y_i, z_i \leq 2000 diapazonundadır, heç bir səthin sahəsi -dən böyük deyil və heç iki səth eyni istiqamətə baxmır. Hər bir kristalın səthləri birlikdə tam qapanmış qabarıq polihedron təşkil edir. Əlavə olaraq, heç bir kristal quruluşunda elə bir degenerasiya yoxdur ki, lazerin neçə səthi eyni anda işıqlandıra biləcəyi haqqında qeyri-müəyyənlik yaransın. Yəni, lazer şüasına paralel səthlərin işığı əks etdirib-etdirməməsi barədə düşünmək lazım deyil — testlər elə qurulub ki, istənilən interpretasiya eyni cavabı verəcəkdir. Giriş ədədi olan sətirlə bitir (bu test halı kimi qəbul edilməməli, sadəcə girişin sonu kimi nəzərə alınmalıdır).
Hər kristal üçün bir sətrdə bir tam ədəd çap et: kristalın lazeri eyni anda ən çox istiqamətə əks etdirə biləcəyi səthlərin maksimum sayı.
Nümunə 1