Balonların Partlaması#3123

Balonların Partlaması

2 saniyə

32 meqabayt

Çətin

Con proqramlaşdırma yarışlarını çox sevir. Ancaq bir problem var: onun komandası proqramlaşdırmada o qədər də yaxşı deyil. Bu adətən onu narahat etmir, amma onu narahat edən odur ki, hər düzgün göndəriş üçün hər kəs bir şar alır. Conun komandası heç vaxt şar almır, digər komandalar isə bir-birinin ardınca şar alır. Bu, onu əsəbləşdirir və Con istəyir ki, digər komandaların da heç şarı olmasın.

Bu il o, bir plan düşünüb. Con bütün şarları partlatması üçün bir ninja tutub. Yarış zamanı istənilən an o, ninjanı tavanın ortasındakı deşikdən aşağı çağırıb, ninja isə shurikenləri (ninja ulduzları) ilə bütün şarları partladıb, yenidən deşikdən çıxa bilər. Əlbəttə, ninja öz qiymətli shurikenlərinin mümkün qədər azını istifadə etmək istəyir. Buna görə də Con bir proqram yazmalıdır ki, bütün şarları partlatmaq üçün neçə shuriken lazım olacaq. Çünki bütün şarlar adətən təxminən eyni hündürlükdə olur, o, bu problemi ikiölçülü kimi modelləşdirə bilər. Ninja görünən yeri $(0, 0)$ başlanğıc nöqtəsi kimi götürür və şarları dairələr şəklində modelləşdirir. Təhlükəsiz olmaq üçün bu dairələrin radiusları müxtəlif ola bilər. Shurikenlər başlanğıcdan atılır və düz xətt üzrə hərəkət edir. Bu xəttin kəsdiyi istənilən dairə/şar partlayacaq. Sual belədir: bütün dairələri kəsmək üçün başlanğıcdan keçən ən az neçə xətt lazımdır?

Yuxarıda qeyd olunduğu kimi, Con yaxşı proqramçı deyil, ona görə də o, bu proqramı yazmaqda sizdən kömək istəyir. Ona kömək edə bilərsinizmi? Düz yazsanız, bəlkə siz də bir şar alarsınız...

Şəkil 1. İkinci nümunə vəziyyəti

Giriş

Girişin birinci sətrində bir tam ədəd var: ardınca gələn testlərin sayı. Hər bir test aşağıdakı formatda verilmişdir:

Bir sətirdə bir tam ədəd $n$ ( $0 \leq n \leq 1000$ 0 \le n \le 1\,000): şarların sayı.
Ardınca $n$ sətir, hər biri üç tam ədəd $x_{i}$ x_i, $y_{i}$ y_i ( $- 1 0^{4} \leq x_{i}, y_{i} \leq 1 0^{4}$ -10^4 \le x_i, y_i \le 10^4), və $r_{i}$ r_i ( $1 \leq r_{i} \leq 1 0^{4}$ 1 \le r_i \le 10^4) verir. $i$ -ci şarın mərkəzi $(x_{i}, y_{i})$ (x_i, y_i) koordinatında, radiusu isə $r_{i}$ r_i-dir.

Aşağıdakilari fərz edə bilərsiniz: iki (başlanğıcı orijində olan) xətt iki müxtəlif dairəyə toxunduqda orijində bu xətlər arasında ən azı $1 0^{- 6}$ 10^{-6} radiyan fərq var. Bundan əlavə, heç iki dairə kəsişmir (ancaq toxuna bilərlər) və heç bir dairə orijini daxil etmir.

Çıxış

Hər bir test üçün bir tam ədəd çap edin: ninjanın bütün şarları partlatmaq üçün minimum neçə shurikenə ehtiyacı var.

Nümunələr

Nümunə 1