grendizer

Grendizer

== include(page="template/taskheader" task_id="grendizer") ==

Poveste şi cerinţă...

Grendizer, robotul din serialul de desene animate urmărit de Algorel în prag de Stele, are o nouă armă. Această armă funcţionează în felul următor: Grendizer işi stabileşte un punct de detonare şi o rază de acţiune $K$; toate obiectivele aflate la distanţa Manhattan exact $K$ faţă vor fi lovite.
 
Algorel a inventariat cele N obiective pe care Grendizer le are de distrus într-unul din episoade. Acum îşi pune întrebări de genul: dacă Grendizer detonează arma în punctul (x, y) cu raza de actiune K, câte din obiective vor fi lovite?
 
Cred că deja ştiţi cine trebuie să rezolve problema în locul obraznicului Algorel - care nu mai ştie niciun algoritm de când cu desenele animate.

h2. Date de intrare

Fişierul de intrare $grendizer.in$ ...

Fişierul de intrare $grendizer.in$ conţine pe prima linie două numere naturale, N si M, reprezentând numarul de obiectiv respectiv numarul de intrebari pentru care Algorel vrea sa afle raspunsul. Urmeaza N linii ce contin cate doua numere intregi reprezentand coordonatele unui obiectiv. Urmatoarele M linii descriu cate o intrebare prin trei numere separate prin spatii: x y K avand semnificatia de mai sus.

h2. Date de ieşire

În fişierul de ieşire $grendizer.out$ ...

În fişierul de ieşire $grendizer.out$ veti afisa M linii cu raspunsul pentru fiecare din cele M intrebari.

h2. Restricţii

* $... ≤ ... ≤ ...$

* Obiectivele se pot suprapune
* Distanta Manahattan intre doua puncte $(x{~1~}, y{~1~})$ si $(x{~2~}, y{~2~})$ este $|x{~1~} - x{~2~}| + |y{~1~} - y{~2~}|$
* Urmatorul tabel specifică valorile pentru N, M si MAX_MOD (punctele vor avea coordonate in intervalul [-MAX_MOD, +MAX_MOD]) pentru fiecare din teste:
 
table(numbers). |_. Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|_. N | x | x | x | x | x | x | x | x | x | x |
|_. M | x | x | x | x | x | x | x | x | x | x |
|_. MAX_MOD | x | x | x | x | x | x | x | x | x | x |

h2. Exemplu