RFID-lərin izlənməsi
Jeroen, Şimal-Qərb Elektrik Resursları Şirkəti (NWERC) üçün anbar saxlama obyektini idarə edir. Müştəri NWERC-ə sifariş verdikdə, bu sifariş anbarda qəbul edilir. Jeroen-in vəzifəsi sifariş edilən məhsulları tapmaq, onları qutuya yığmaq və müştəriyə göndərməkdir.
NWERC-in qeyri-adi anbar siyasəti var: məhsullar müəyyən bir qaydada düzülməyib və hər yerdə səpələnib. Lakin, Jeroen işini görə bilir, çünki hər bir məhsul RFID texnologiyası ilə izlənilir. Xüsusilə, hər bir məhsula anbara daxil olduqdan dərhal sonra simsiz RFID çipi təyin edilir və anbar tavanında yerləşən sensorlar məhsulları avtomatik izləmək üçün istifadə olunur.
Varsayılan olaraq, hər bir sensorun r vahid məsafəsi var - yəni, o, ən çox r vahid məsafədə yerləşən hər hansı bir RFID çipini oxuya bilər. Lakin, bir sensor ilə məhsul arasındakı xətt seqmenti x divarlarla kəsişirsə və ya toxunursa, sensorun həmin istiqamətdəki məsafəsi x vahid azalır. Bundan əlavə, sensorlar digər sensorlardan gələn müdaxilə səbəbindən RFID çipini oxuya bilməzlər, buna görə də anbarda hər hansı bir sensor cütü arasındakı məsafə ən azı r vahid olmalıdır. Siz əlavə olaraq heç bir sensorun və ya məhsulun divarda yerləşdirilmədiyini fərz edə bilərsiniz.
Jeroen indi hər bir məhsul üçün hansı sensorların onun RFID çipini oxuya biləcəyini müəyyən etmək istəyir. Ona kömək edə bilərsinizmi?
Nümunə Girişdəki sensorlar, divarlar və məhsulların təsviri.
Giriş verilənləri
Birinci sətirdə bir müsbət tam ədəd: test halların sayı, ən çox 100. Hər test halı üçün:
dörd tam ədəd s (1 ≤ s ≤ 250000), r (1 ≤ r ≤ 20), w (0 ≤ w ≤ 10) və p (1 ≤ p ≤ 10000) olan bir sətir, burada s sensorların sayını, r hər bir sensorun məsafəsini, w divarların sayını və p məhsulların sayını təmsil edir.
s sətir, hər biri iki tam ədəd x_i və y_i (-10000 ≤ x_i, y_i ≤ 10000) ehtiva edir. Hər belə sətir (x_i, y_i) yerində bir sensoru təmsil edir. Hər hansı bir sensor cütü arasındakı məsafə ən azı r vahid olacağına zəmanət verilir.
w sətir, hər biri dörd tam ədəd bx_i, by_i, ex_i və ey_i (-10000 ≤ bx_i, by_i, ex_i, ey_i ≤ 10000) ehtiva edir. Hər belə sətir (bx_i, by_i) ilə (ex_i, ey_i) arasında düz xətt seqmenti kimi qəbul edilməli olan bir divarı təmsil edir. Bu xətt seqmentinin uzunluğu müsbət olacaq.
p sətir, hər biri iki tam ədəd px_i və py_i (-10000 ≤ px_i, py_i ≤ 10000) ehtiva edir. Hər belə sətir (px_i, py_i) yerində bir məhsulu təmsil edir.
Çıxış verilənləri
Hər test halı üçün:
p sətir, girişdə göründükləri sırayla hər bir məhsulu təmsil edir. Hər sətir bir tam ədəd t ehtiva etməlidir, məhsulu izləyə bilən sensorların sayını; bu tam ədəd daha sonra müvafiq sensor yerlərini təmsil edən t cütlər siyahısı ilə izlənməlidir. Bir neçə sensor varsa, onlar x koordinatına görə artan sırayla sıralanmalıdır. Bir neçə sensor eyni x koordinatına malikdirsə, onlar y koordinatına görə artan sırayla sıralanmalıdır.