Fişierul intrare/ieşire:nori.in, nori.outSursăPreOJI 2017
AutorMarius NicoliAdăugată demihaipopa12Popa Mihai mihaipopa12
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nori

Pentru ca a sosit vacanta, merg iar în vizită la bunici, lângă Dunăre. Şi pentru că vine ploaia, cu tunete şi fulgere, aud iarăşi loviturile de tun ale vecinilor bulgari, care, pentru a-şi proteja culturile de castraveţi de grindină trebuie să spargă norii ameninţători. Vreau acum sa aflu, pentru fiecare direcţie posibilă de lansare a unei lovituri, dacă aceasta atinge sau nu vreun nor. Considerăm că norii au formă circulară, iar o lovitură de tun trimite proiectilul pe direcţia unei drepte.
Formal, se dau N cercuri complet incluse în cadranul 1 al unui sistem ortogonal de axe şi M semidrepte care pleacă din origine şi trec prin cadranul 1.
Determinaţi, pentru fiecare dintre semidrepte, dacă intersectează cel puţin un cerc.

Date de intrare

Fişierul nori.in are structura: pe prima linie N, numărul de nori; pe fiecare dintre următoarele N linii câte 3 numere naturale separate prin câte un spaţiu reprezentând un cerc (în ordine, abscisa centrului, ordonata centrului, raza); pe linia următoare M, numărul de lansări; pe fiecare dintre următoarele M linii câte 2 numere naturale nenule separate printr-un spaţiu, x şi y cu semnificaţia: lansarea se face din originea sistemului ortogonal pe direcţia unei drepte ce trece prin punctul de coordonate (x, y).

Date de ieşire

Pe prima linie a fişierului nori.out se află M valori 0 şi 1, neseparate prin spaţii. A k – a valoare este 1 dacă dreapta k din fişierul de intrare nu intersectează niciun cerc şi 0 dacă intersectează cel puţin un cerc.

Restricţii

  • 1 ≤ N, M ≤ 100000
  • Celelalte valori din fişierul de intrare sunt numere pozitive nenule mai mici sau egale cu 10000
  • Cercurile se pot intersecta şi pot fi chiar cercuri identice
  • Semidreptele nu sunt neapărat distincte şi sunt infinite
  • O semidreaptă intersectează un cerc dacă are cel puţin un punct comun cu el.

Exemplu

nori.innori.out
2
8 2 1
2 8 1
6
8 2
8 3
2 8
1 1
1 100
100 1
000111
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?