Sferaları Miras Al#3202

Sferaları Miras Al

1 saniyə

64 meqabayt

Çox çətin

$2 xxx$ -ci ildə bir ekspedisiya qrupu bir planetə enərək orada həmin planetdə yaşamış qədim bir növə aid qəribə obyektlər aşkarladı. Bunlar qeyri-şəffaf bərk kürələrdən ibarət şəffaf qutulardır (Şəkil 1). Bundan başqa, kürələrin mövqeləri və radiuslarını ehtiva edən çoxlu litograflar da tapıldı.

Şəkil 1. Qəribə obyekt

Əvvəldə bu obyektlərin nə üçün hazırlandığı məlum deyildi, lakin professor Zambendorf aşkar etdi ki, üfüqi bir müstəvinin yaratdığı kəsik böyük rol oynayır. Məsələn, obyektin kəsiyi, müstəvi altdan yuxarıya doğru sürüşdürülərkən, Şəkil 2-dəki kimi dəyişir.

Şəkil 2. Müxtəlif mövqelərdə alınan kəsiklər

O nəhayət aşkar etdi ki, bəzi məlumatlar kəsikdə birləşik fiqurların (komponentlərin) sayının dəyişməsi vasitəsilə ifadə olunur, burada hər bir birləşik fiqur toxunan və ya kəsişən disk birləşməsidir və hər bir disk müvafiq bərk kürənin kəsiyidir. Məsələn, daha sonra verilən nümunəyə aid Şəkil 2-də birləşik fiqurların sayı $z = 0.0000$ z = 0.0000, $162.0000$ , $167.0000$ , $173.0004$ , $185.0000$ , $191.9996$ , $198.0000$ , $203.0000$ və $205.0000$ nöqtələrində ardıcıllıqla $0$ , $1$ , $2$ , $1$ , $2$ , $3$ , $2$ , $1$ və $0$ olur. Artım üçün $1$ , azalma üçün isə $0$ təyin etsək, bu keçidlər $8$ -bitlik ikilik ədəd $11011000$ kimi təsvir oluna bilər.

Daha ətraflı analiz üçün, müstəvi altdan $(z = 0)$ (z = 0) yuxarıya $(z = 36000)$ (z = 36000) doğru sürüşdürülərkən bu keçidləri müəyyən edən proqram yazın.

Giriş

Giriş bir neçə datasetdən ibarətdir. Hər bir dataset bir sətirdə olan və həmin datasetdəki kürələrin sayını bildirən müsbət tam ədəd ilə başlayır. Sonra $N$ sətirində kürələrin mərkəz və radiuslarını təsvir edən məlumatlar gəlir. Hər bir sətirdə dörd müsbət tam ədəd $X_{i}$ X_i, $Y_{i}$ Y_i, $Z_{i}$ Z_i, və $R_{i}$ R_i ( $i = 1, \dots, N$ i = 1, \ldots, N) — $i$ -ci kürənin mərkəzi və radiusu — verilir.

Aşağıdakıları qəbul edə bilərsiniz: $1 \leq N \leq 100$ 1 \leq N \leq 100, $1 \leq R_{i} \leq 2000$ 1 \leq R_i \leq 2000, $0 < X_{i} - R_{i} < X_{i} + R_{i} < 4000$ 0 < X_i - R_i < X_i + R_i < 4000, $0 < Y_{i} - R_{i} < Y_{i} + R_{i} < 16000$ 0 < Y_i - R_i < Y_i + R_i < 16000, $0 < Z_{i} - R_{i} < Z_{i} + R_{i} < 36000$ 0 < Z_i - R_i < Z_i + R_i < 36000. Hər bir bərk kürə $(x, y, z)$ (x, y, z) nöqtələri üçün $(x - X_{i})^{2} + (y - Y_{i})^{2} + (z - Z_{i})^{2} \leq R_{i}^{2}$ (x - X_i)^2 + (y - Y_i)^2 + (z - Z_i)^2 \leq R_i^2 bərabərsizliyini ödəyir.

Bir kürə digər kürələri daxilində saxlaya bilər. Heç bir iki kürə bir-birinə toxunmur. Hər bir $Z_{i} \pm R_{i}$ Z_i \pm R_i və iki kürənin kəsişməsində yaranan dairənin ən kiçik/böyük $z$ koordinatı bir-birindən ən azı $0.01$ fərqlənir.

Girişin sonu bir sətrdə tək sıfırla göstərilir.

Çıxış

Hər bir dataset üçün proqramınız iki sətir çıxarmalıdır. Birinci sətirdə keçidlərin sayı $M$ olmalıdır. İkinci sətirdə isə bu keçidləri yuxarıda təsvir olunduğu kimi göstərən $M$ -bitlik ikilik ədəd verilməlidir.

Nümunələr

Nümunə 1