Fişierul intrare/ieşire:katyusha.in, katyusha.outSursăInfoOltenia 2018 - Clasele 11 - 12 Echipe
AutorBogdan Iordache, Murtaza AlexandruAdăugată deinfoolteniaInfo-Oltenia 2018 infooltenia
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Katyusha

"Aruncătoarele de proiectile reactive Katyusha sunt un tip de artilerie reactivă construite şi folosite pentru prima dată de Uniunea Sovietică începând cu al Doilea Război Mondial. În comparaţie cu alte piese de artilerie, aceste lansatoare multiple de rachete pot satura rapid o ţintă cu o cantitate mare de explozivi, însă au o precizie mai redusă şi necesită un timp mai mare de reîncărcare."

Aveţi în faţa voastră un câmp de bătălie, reprezentat prin planul cartezian. Există N vehicule inamice, reprezentate prin puncte, care se deplasează în linie dreaptă şi cu viteză constantă. Pentru fiecare vehicul se cunosc: poziţia la momentul iniţial (T=0), poziţia la care se va afla după o unitate de timp şi costul acestuia.

Aveţi la dispoziţie o baterie de Katyusha şi M opţiuni de tragere reprezentate prin cercuri în planul cartezian, pe care le vom numi mai simplu ţinte. Pentru o opţiune de tragere, se poate alege momentul de timp (mai mare sau egal cu 0, nu neapărat întreg) la care aceasta să se execute, toate vehiculele aflate la momentul respectiv în interiorul ţintei vor fi distruse, inamicului aducându-i-se o pagubă egală cu suma costurilor vehiculelor distruse.

Pentru fiecare posibilitate de tragere, calculaţi, în cazul în care aceasta ar fi aleasă, care este suma maximă
posibilă a costurilor vehiculelor distruse.

Date de intrare

Prima linie a fişierului katyusha.in va conţine două numere naturale N şi M, cu semnificaţia din enunţ.
Pe fiecare dintre următoarele N linii, se vor găsi în ordine următoarele: două numere reale x0 , y0 (poziţia iniţială a unui vehicul), două numere reale x1 , y1 (poziţia după o unitate de timp a vehiculului), un număr întreg v (costul vehiculului).
Pe fiecare dintre următoarele M linii, se vor găsi trei numere reale: x, y, r, reprezentând câte o ţintă (centru (x, y) şi rază r).

Date de ieşire

Pe fiecare din primele M linii ale fişierului katyusha.out afişaţi suma maximă posibilă a costurilor vehiculelor distruse pentru fiecare opţiune de tragere, în parte.

Restricţii

  • 1 ≤ N * M ≤ 300000
  • -109 ≤ x0, y0, x1, y1, x, y, r ≤ 109
  • 1 ≤ v ≤ 3000
  • pentru 45% din teste 1 ≤ N, M ≤ 200

Exemplu

katyusha.inkatyusha.out
3 2
0.0 0.0 3.0 3.0 7
3.0 1.5 3.0 1.5 2
0.0 5.0 1.0 5.0 10
2.0 2.0 2.0
3.0 1.0 1.4143
9
9

Explicaţie

Prima tragere se poate efectua la momentul 0.5.
A doua tragere se poate efectua la momentul 0.662981.
În ambele cazuri sunt distruse vehiculele 1 şi 2 ce însumează pagube de valoare totală 9.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?