Fişierul intrare/ieşire:	nori.in, nori.out	Sursă	PreOJI 2017
Autor	Marius Nicoli	Adăugată de	Popa Mihai •mihaipopa12
Timp execuţie pe test	0.25 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/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

Cum se trimit solutii?