Fişierul intrare/ieşire:nuke.in, nuke.outSursăLot Vrancea 2010, Baraj 2
AutorCosmin Gheorghe, Victor RusuAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.innuke.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content