Hava Hücumu#1276
General Gi bir hərbi bazanın komandiridir. O, casuslarından biri tərəfindən qorxulu bir xəbər alıb: düşmən hava raket zərbəsinə hazırlaşır. Bazada iki maqnit qülləsi var. Bu qüllələr aktiv ediləndə və kifayət qədər enerji verildikdə, hər biri güclü bir üfüqi maqnit disk əmələ gətirir. Əgər hər hansı bir raket bu diskdən keçərsə, bazadan yayınır.
Bu qüllələr hava hücumundan müdafiə üçün əla kimi görünsə də, bir problem var: bir qüldəinin yaratdığı diskin sahəsi ona verilən enerji ilə mütənasibdir. Bazada elektrik stansiyaları tərəfindən müəyyən miqdarda enerji istehsal olunur və bu enerji iki qüldə arasında bölüşdürülməlidir. Bu o deməkdir ki, qüllələrin yaratdığı iki diskin ümumi sahəsi elektrik stansiyalarının istehsal etdiyi ümumi enerjidən artıq ola bilməz. Xoşbəxtlikdən, casus gələn raketlərin dəqiq hədəf koordinatlarını öyrənə bilib və General Gi-yə məlumat verib. General, iki maqnit qüldəsi arasında enerjinin necə bölüşdürüləcəyi mövzusunda sizdən kömək istəyir ki, bazaya dəyəcək (yəni yayındırıla bilməyəcək) raketlərin sayı minimal olsun. Aşağıdakıları fərz edə bilərsiniz:
Qüllələr müxtəlif hündürlüklərdə yerləşir, buna görə də maqnit disklərinin bir-birinə təsiri yoxdur.
Raket bir qüldəinin maqnit diskindən keçərsə, hətta yalnız sərhədinə toxunsa belə, yayındırılacaq.
Raket məhz qüldəinin yerləşdiyi nöqtəyə düşərsə, hətta qüldəiyə heç enerji verilməsə belə, yayındırılar.
Bütün gələn raketlər eyni anda və eyni anda bazaya çatır, buna görə zərbə zamanı qüllələr arasında enerjini yenidən bölmək mümkün deyil.
Giriş bir neçə test halından ibarətdir. Hər test halı N+2 sətirdən ibarətdir. Birinci sətirdə bir tam ədəd (1 \leq N \leq 1\,000) verilir — raketlərin sayı. İkinci sətirdə həqiqi ədəd X_1, Y_1, X_2, Y_2, T verilir: (X_1, Y_1) birinci qüllənin koordinatları, (X_2, Y_2) ikinci qüllənin koordinatları, isə elektrik stansiyalarının istehsal etdiyi ümumi enerji miqdarıdır (iki maqnit diskin ümumi sahəsi). Növbəti sətirin hər birində bir raketin düşdüyü nöqtənin koordinatları olan iki həqiqi ədəd verilir.
Verilən bütün həqiqi ədədlərin modulu -dən böyük deyil və onluq vergüldən sonra ən çox rəqəm ola bilər. Eyni sətirdə iki ardıcıl ədəd bir və ya daha çox boşluqla ayrılır. Test hallarının arasında istənilən sayda boş sətir ola bilər.
Giriş faylının son sətirində təkcə bir sıfır verilir.
Hər bir test üçün aşağıdakı sətri çap edin:
k. M
Burada test halının nömrəsidir (-dən başlayaraq), isə iki qüldə arasında ən optimal enerji bölgüsündə yayındırıla BİLMƏYƏCƏK minimal raket sayıdır. \pi = 3.141 kimi götürün.
Qeyd: -dən əvvəl bir boşluq simvolu var.
Nümunə 1