Xilasetmə Mayakı
Han Solo, bəzi köhnə və o qədər də xoş olmayan kreditorlarından qaçmağa çalışarkən, Millennium Falcon-u buz dünyası Hoth-da qəzaya uğratdı. İndi o, Wookiee dostu xəz-dondurma halına gəlmədən və ya Hans-kabab yeməyə qərar vermədən əvvəl xilas edilməsi üçün bir növ təcili siqnal işlətməlidir. Ona kömək edə bilərsinizmi?
Han, işıq-illərlə uzaqdan görünə bilən çox parlaq bir lazeri xilas edə bildi və bunun yaxşı bir siqnal olacağını düşündü. Dezavantajı isə odur ki, əgər onu sadəcə göyə doğru parıldatsa, işığın yolunda kimsənin təsadüfən olma ehtimalı çox az olardı. Bu arada, Chewbacca yaxınlıqdakı bir mağarada tapdığı çox əks etdirici, çox üzlü kristallarla oynayırdı. Sonra, bir ilham anında, Han işığı kristalın üzərinə parıldadaraq xilasetmə mayakı qura biləcəyini anladı, kristalın üzləri isə öz növbəsində işığı çoxsaylı istiqamətlərə əks etdirəcək!
Şəkil 1: Han'ın xilasetmə mayakının sadələşdirilmiş, iki ölçülü təsviri.
Yeganə problem hansı kristalın işıq əks etdirici kimi istifadə olunacağını qərarlaşdırmaqdır. Hər bir əks etdirici kristal yalnız mükəmməl üçbucaq üzlərdən ibarət olan konveks çoxüzlü bir formadadır və mayaka istənilən istiqamətdə yerləşdirilə bilər. Əlbəttə ki, istifadə üçün ən yaxşı kristal, lazer şüasını (tək bir istiqamətdən gələn paralel işıq şüalarından ibarət olan) ən çox sayda istiqamətə əks etdirə bilən kristaldır. Başqa sözlə, bir kristalın əks etdirici dəyərini, hər hansı bir baxış istiqamətindən görə biləcəyiniz üzlərin sayı kimi düşünə bilərsiniz, çünki bunlar lazer şüası tərəfindən eyni anda vurula bilən üzlərdir. Hər bir kristalın geometriyasının təsvirini nəzərə alaraq, kristalın lazeri əks etdirə biləcəyi ən çox istiqamət sayını hesablaya bilərsinizmi?
Giriş verilənləri
Giriş, Chewbacca'nın kolleksiyasındakı kristalların geometrik təsvirlərindən ibarət olacaq. Hər bir kristalın təsviri, bir sətirdə kristalın üzlərinin sayı olan n (4 ≤ n ≤ 2000) tam ədədi ilə başlayır, ardınca isə n sətir üzləri təsvir edir. Hər bir üz 9 tam ədədlə təsvir olunur, x_1 y_1 z_1 x_2 y_2 z_2 x_3 y_3 z_3, burada üç ölçüdəki nöqtələr (x_1, y_1, z_1), (x_2, y_2, z_2) və (x_3, y_3, z_3) xaricdən baxıldığında saat əqrəbi istiqamətində olmayan sırada üçbucaq üzün təpələrini təşkil edir. Bütün koordinatlar -2000 ≤ x_i, y_i, z_i ≤ 2000 aralığında yerləşir, heç bir üzün səth sahəsi 200000-dən böyük deyil və heç iki üz eyni istiqamətə baxmır. Hər bir kristalın bütün üzləri birləşdirildikdə, qapalı konveks çoxüzlü əmələ gətirir. Nəhayət, heç bir kristalın strukturu lazerin neçə üzə dəyə biləcəyinə dair qeyri-müəyyənlik yaradan hər hansı bir degenerasiyaya malik olmayacaq. Başqa sözlə, lazer şüasına paralel olan üzlərin şüanı əks etdirə biləcəyini nəzərə alıb-almamağınızın əhəmiyyəti yoxdur - test məlumatları hər iki şərhin eyni cavabı verəcəyi şəkildə qurulmuşdur. Başqa sözlə, lazer şüasına paralel olan üzlərin işığı əks etdirə biləcəyini nəzərə alıb-almamağınızın əhəmiyyəti yoxdur. Giriş, bir sətirdə 0 rəqəmi ilə bitir (bunu test halı kimi emal etməyin).
Çıxış verilənləri
Hər bir kristal üçün, lazer şüasını eyni anda əks etdirə biləcəyi ən çox istiqamət sayını göstərən bir tam ədəd m olan bir sətir çıxarın.