Fişierul intrare/ieşire:nn.in, nn.outSursăGrigore Moisil 2016, Clasa a 10-a
AutorPetru TrimbitasAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test1.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

NN

Marele inginer NN, expert în construirea de baraje, a primit de data aceasta o sarcină mai îmbârligată. Acesta are de construit M baraje peste mai multe râuri dintr-o deltă şi îşi planifică pe hârtie milimetrică construcţia fiecărui baraj în parte.
Toate râurile peste care are de construit baraje sunt braţe ale aceluiaşi fluviu şi toate pornesc din exact acelaşi punct pe lungimea fluviului. Pentru a-şi explica schiţa, NN marchează locul de despărţire a tuturor braţelor fluviului printr-un punct O, numit origine. Apoi, din origine pornesc N semidrepte, fiecare reprezentând o porţiune de uscat, astfel încât spaţiul gol dintre 2 semidrepte consecutive va fi considerat un braţ al fluviului.
După ce a desenat schiţa proiectului, NN se întreabă care e numărul de râuri pe care le acoperă complet fiecare baraj. Un baraj acoperă complet un râu dacă intersectează fiecare dintre malurile acestuia. Sarcina voastră este să îl ajutaţi oferindu-i informaţii precise pentru a-şi putea realiza planul cât mai eficient, păstrându-şi renumele.

Date de intrare

Pe prima linie a fişierului nn.in se află N şi M, reprezentând numărul de semidrepte, respectiv numărul de baraje. Pe fiecare dintre următoarele N linii se vor afla informaţii despre cele N semidrepte, astfel: pe linia i (1 ≤ i ≤ N) se află o pereche de numere naturale x şi y, reprezentând coordonatele unui punct aflat pe semidreapta i (ştim deja că toate semidreptele pornesc din O(0, 0)). Pe fiecare dintre următoarele M linii se vor afla câte 4 numere x1, y1, x2, y2 reprezentând faptul că există un baraj care are extremităţile în punctele de coordonate (x1, y1) şi (x2, y2).

Date de ieşire

În fişierul de ieşire nn.out se vor afişa M numere, fiecare pe o linie separată, reprezentând numărul de râuri blocate de fiecare dintre cele M baraje. În rezolvarea problemei nu se va ţine cont de grosimea barajului, aceasta fiind neglijabilă.

Restricţii

  • Toate numerele din fişierul de intrare sunt naturale ≤ 105
  • Nici un punct din fişier nu coincide cu originea
  • Pentru 10% din teste N = 2, M = 1
  • Pentru următoarele 20% din teste, capetele segmentelor (barajelor) se vor afla pe semidreptele din datele de intrare
  • Pentru primele 50% din teste N, M ≤ 1000
  • Se recomanda folosirea tipului long double pentru lucrul cu numere rationale.

Exemplu

nn.innn.out
5 3
5 1
2 1
2 5
5 5
0 4
3 0 4 2
1 4 3 1
5 3 7 6
1
2
0

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?