Balonların Partlaması
John proqramlaşdırma müsabiqələrini sevir. Ancaq bir problem var: onun komandası proqramlaşdırmada çox yaxşı deyil. Bu, adətən onu narahat etmir, amma onu narahat edən şey hər düzgün təqdimat üçün hər kəsin bir şar almasıdır. John's komandası heç vaxt şar almır, digər komandalar isə bir-birinin ardınca şar alır. Bu onu əsəbiləşdirir, ona görə də John istəyir ki, digər komandaların da şarları olmasın.
Bu il o, bunu həyata keçirmək üçün bir plan hazırlayıb. John bütün şarları partlatmaq üçün bir ninza işə götürüb. Müsabiqə zamanı istənilən vaxt, o, ninzanı tavandakı bir dəlikdən aşağı çağırıb, şurikenlərindən (ninza ulduzları) istifadə edərək bütün şarları partlatmasını təmin edə bilər, sonra yenidən tavandakı dəlikdən çıxar. Təbii ki, ninza öz qiymətli şurikenlərindən mümkün qədər az istifadə etmək istəyir. Buna görə də, John bütün şarları partlatmaq üçün neçə şuriken lazım olduğunu hesablayan bir proqram yazmalıdır. Çünki bütün şarlar adətən təxminən eyni hündürlükdədir, o, problemi 2-ölçülü problem kimi modelləşdirə bilər. Ninzanın yerini (gəldiyi yeri) başlanğıc nöqtəsi (0, 0) kimi təyin edir və şarları modelləşdirmək üçün dairələrdən istifadə edir. Təhlükəsiz olmaq üçün, bu dairələrin müxtəlif radiusları ola bilər. Şurikenlərin başlanğıc nöqtəsindən atıldığı və düz xətt boyunca hərəkət etdiyi qəbul edilir. Bu xəttin kəsdiyi hər hansı dairə/şar bu şuriken tərəfindən partladılacaq. Sual belə olur: bütün dairələri kəsmək üçün başlanğıc nöqtəsində köklənmiş neçə xətt lazımdır?
Təbii ki, yuxarıda qeyd edildiyi kimi, John çox yaxşı proqramçı deyil, ona görə də sizdən bu proqramı onun üçün hazırlamağınızı xahiş edir. Ona kömək edə bilərsinizmi? Əgər düzgün etsəniz, bir şar ala bilərsiniz...
Şəkil 1. İkinci nümunə halı
Giriş verilənləri
Girişin ilk sətri bir ədəd ehtiva edir: izlənəcək test hallarının sayı. Hər bir test halı aşağıdakı formatda olur:
Bir sətirdə tək ədəd n (0 ≤ n ≤ 1,000): şarların sayı.
n sətir, hər biri üç ədəd x_i, y_i (-10^4 ≤ x_i, y_i ≤ 10^4) və r_i (1 ≤ r_i ≤ 10^4) ehtiva edir, i-ci şarı modelləşdirmək üçün istifadə olunan dairəni təsvir edir, burada (x_i, y_i) dairənin mərkəzidir və r_i radiusdur.
İki xəttin (başlanğıc nöqtəsində köklənmiş) iki fərqli dairəyə toxunan xətlərin başlanğıc nöqtəsində ən az 10^{-6} radian bucaq yaratdığını qəbul edə bilərsiniz. Üstəlik, dairələr bir-birini kəsmir (amma toxuna bilər) və başlanğıc nöqtəsini ehtiva etmir.
Çıxış verilənləri
Girişdəki hər bir test halı üçün çıxış bir sətirdə bir ədəd olmalıdır: ninzanın bütün şarları partlatmaq üçün lazım olan minimum şuriken sayı.