Sferaları Miras Al
İl 2xxx-də, bir ekspedisiya qrupu bir planetə enərək, o planetdə yaşayan qədim bir növ tərəfindən hazırlanmış qəribə obyektlər tapdı. Bunlar qeyri-şəffaf bərk kürələrdən ibarət şəffaf qutulardır (Şəkil 1). Həmçinin, kürələrin mövqelərini və radiuslarını ehtiva edən çoxlu litoqraflar da var.
Şəkil 1. Qəribə obyekt
Əvvəlcə onların məqsədi naməlum idi, lakin Professor Zambendorf üfüqi bir təbəqə ilə əmələ gələn kəsiklərin mühüm rol oynadığını aşkar etdi. Məsələn, bir obyektin kəsiyi Şəkil 2-də göstərildiyi kimi təbəqəni aşağıdan yuxarıya sürüşdürməklə dəyişir.
Şəkil 2. Müxtəlif mövqelərdə kəsiklər
O, nəhayət, bəzi məlumatların kəsikdəki birləşmiş fiqurların sayının keçidi ilə ifadə edildiyini tapdı, burada hər bir birləşmiş fiqur bir-birinə toxunan və ya kəsişən disklərin birliyidir və hər bir disk müvafiq bərk kürənin kəsiyidir. Məsələn, Şəkil 2-də, daha sonra ilk nümunə datasetində təsvir edilən geometriyada, birləşmiş fiqurların sayı 0, 1, 2, 1, 2, 3, 2, 1 və 0 olaraq dəyişir, müvafiq olaraq z = 0.0000, 162.0000, 167.0000, 173.0004, 185.0000, 191.9996, 198.0000, 203.0000 və 205.0000-də. Artımı 1 və azalmayı 0 olaraq təyin edərək, bu ardıcıllığın keçidləri 8-bitlik ikilik ədəd 11011000 ilə ifadə edilə bilər.
Daha ətraflı analizə kömək etmək üçün, üfüqi təbəqəni aşağıdan (z = 0) yuxarıya (z = 36000) sürüşdürərkən keçidləri müəyyən edən bir proqram yazın.
Giriş verilənləri
Giriş bir sıra datasetlərdən ibarətdir. Hər bir dataset müsbət bir tam ədədlə başlayır, bu ədəd datasetdəki kürələrin sayını N göstərir. Ardınca kürələrin mərkəzlərini və radiuslarını təsvir edən N sətir gəlir. Hər bir N sətir i-ci kürənin mərkəzini və radiusunu təsvir edən dörd müsbət tam ədəd X_i, Y_i, Z_i və R_i (i = 1, ..., N) ehtiva edir.
1 ≤ N ≤ 100, 1 ≤ R_i ≤ 2000, 0 < X_i - R_i < X_i + R_i < 4000, 0 < Y_i - R_i < Y_i + R_i < 16000, və 0 < Z_i - R_i < Z_i + R_i < 36000 olduğunu qəbul edə bilərsiniz. Hər bir bərk kürə (x, y, z) nöqtələrinin (x - X_i)^2 + (y - Y_i)^2+ (z - Z_i)^2 ≤ R_i^2 şərtini ödədiyi nöqtələr dəstəsi kimi müəyyən edilir.
Bir kürə digər kürələri ehtiva edə bilər. Heç iki kürə qarşılıqlı toxunmur. Hər bir Z_i ± R_i və hər hansı iki kürənin kəsişməsi ilə əmələ gələn dairənin minimum/maksimum z koordinatları bir-birindən ən az 0.01 fərqlənir.
Girişin sonu bir sıfır ilə göstərilir.
Çıxış verilənləri
Hər bir dataset üçün, proqramınız iki sətir çıxarmalıdır. Birinci sətir keçidlərin sayını göstərən bir tam ədəd M ehtiva etməlidir. İkinci sətir isə yuxarıda göstərildiyi kimi birləşmiş fiqurların sayının keçidlərini ifadə edən M-bitlik ikilik ədəd ehtiva etməlidir.