| Fişierul intrare/ieşire: | nuke.in, nuke.out | Sursă | Lot Vrancea 2010, Baraj 2 |
| Autor | Cosmin Gheorghe, Victor Rusu | Adăugată de |  Andrei Misarca •Mishu91 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Nuke
Teritoriul Metalopolis poate fi văzut ca un plan cartezian. În acest teritoriu, Zeratul a reuşit să infiltreze N soldaţi invizibili cu misiunea de a învinge forţele inamicului său, Jim Raynor. Soldaţii pot fi consideraţi puncte de coordonate (XS, YS) întregi. Pentru a se apăra, Jim Raynor lansează M bombe nucleare. Bomba i elimină toţi soldaţii aflaţi la o distanţă mai mică sau egală cu Ri de punctul (XBi , YBi) în care a explodat. Pentru a maximiza eficienţa atacului, Raynor are grijă ca nicio zonă din Metalopolis să nu fie afectată decât de cel mult o bombă nucleară. Pentru fiecare bombă i Zeratul doreşte să ştie câţi soldaţi a pierdut.
Având la dispoziţie coordonatele celor N soldaţi, coordonatele şi razele de acţiune ale celor M bombe, aflaţi pentru fiecare bombă câţi soldaţi elimină.
Date de intrare
Pe prima linie a fişierului nuke.in se dau două numere naturale N şi M cu semnificaţia din enunţ. Urmatoarele N linii conţin fiecare câte două numere întregi XSi , YSi reprezentând coordonatele soldaţilor. Următoarele M linii conţin câte trei numere întregi XBi , YBi , Ri reprezentând coordonatele şi raza fiecărei bombe.
Date de ieşire
În fişierul de ieşire nuke.out veţi afişa M linii, pe fiecare linie i aflându-se câte un singur număr natural reprezentând numărul de soldaţi eliminaţi de bomba i. Bombele se consideră în ordinea în care apar în fişierul de intrare.
Restricţii
- 1 ≤ N ≤ 200.000
- 1 ≤ M ≤ 100.000
- 1 ≤ Ri ≤ 1.000.000.000
- -1.000.000.000 ≤ XBi , YBi , XSi , YSi ≤ 1.000.000.000
- Un soldat aflat la o distanţă egală cu Ri de bomba i va fi eliminat
- Suprafeţele de acţiune ale oricăror două bombe nu au niciun punct în comun.
Exemplu
| nuke.in | nuke.out |
|---|---|
| 7 3 4 5 0 5 -1 6 5 1 -1 -2 -3 6 1 4 5 4 3 1 1 1 -1 6 2 | 2 0 3 |
Explicaţie
Prima bombă elimină soldaţii (4, 5), (5, 1).
A doua bombă nu elimină niciun soldat.
A treia bombă elimină soldaţii (0, 5), (-1, 6) şi (-3, 6).
