Asteroid Rangers
İl 2112-dir və insanlıq artıq Günəş sistemini fəth edib. Kosmik Qoruyucu Korpusu, yaşayış üçün az da olsa uyğun olan hər hansı bir səthdə bazalar qurub. Asteroidlər üzrə Rabitə Nazirliyinin üzvü olaraq sizin vəzifəniz, Kosmik Qoruyucu asteroid bazalarının bir-biri ilə mümkün qədər ucuz şəkildə əlaqə qura bilməsini təmin etməkdir. Hər bazadan digər bazalara birbaşa rabitə bağlantıları qurmaq mümkündür, lakin bu, çox baha başa gələrdi. Bunun əvəzinə, hər kəsin bir və ya daha çox baza vasitəsilə mesaj göndərə bilməsi üçün minimum sayda bağlantı qurmaq istəyirsiniz. Hər hansı bir bağlantının dəyəri, birləşdirdiyi iki baza arasındakı məsafə ilə birbaşa mütənasibdir, buna görə də bu problem çox çətin görünmür.
Lakin, kiçik bir çətinlik var. Asteroidlər hərəkət etməyə meyllidir, belə ki, hazırda çox yaxın olan iki baza gələcəkdə belə olmaya bilər. Buna görə də zaman keçdikcə rabitə bağlantılarınızı dəyişdirməyə hazır olmalısınız ki, həmişə ən ucuz ötürücü sistemə sahib olasınız. Bu bağlantıları dəyişdirmək vaxt və pul tələb edir, buna görə də belə bir dəyişiklik etməli olduğunuz halların sayını bilmək istəyirsiniz.
Bəzi fərziyyələr işinizi asanlaşdırır. Hər bir asteroid tək bir nöqtə kimi qəbul edilir. Asteroidlər həmişə sabit sürətlə xətti hərəkət edir. Heç bir asteroid digər asteroidlərlə toqquşmur. Həmçinin, t ≥ 0 zamanında optimal olan hər hansı bir ötürücü sistem, t < s < t+10 şərtini ödəyən hər hansı bir zaman üçün unikal olaraq optimal olacaq. İlkin optimal ötürücü sistem unikal olacaq.
Giriş verilənləri
Hər test halı, asteroid bazalarının sayını göstərən bir tam ədəd n (2 ≤ n ≤ 50) olan bir sətirlə başlayır. Bundan sonra n sətir gəlir, hər biri altı tam ədəd x, y, z, v_x, v_y, v_z ehtiva edir. İlk üçü bir asteroidin ilkin yerini göstərir (-150 ≤ x, y, z ≤ 150), son üçü isə həmin asteroidin kosmos vahidləri ilə zaman vahidi başına x, y və z sürət komponentlərini göstərir (-100 ≤ v_x, v_y, v_z ≤ 100).
Çıxış verilənləri
Hər test halı üçün, bir sətirdə hal nömrəsini və ötürücü sistemin qurulması və ya dəyişdirilməsi lazım olan halların sayını göstərin.