Fişierul intrare/ieşire:elmer.in, elmer.outSursăONI 2016, clasa a 10-a
AutorMircea PopoveniucAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Elmer

În antrenamentul său intens pentru prinderea lui Daffy Duck, celebrul vânător Elmer Fudd a început să vâneze raţe în oraşul său preferat, Craiova. Se ştie că există N raţe reprezentate prin puncte în planul de coordonate xOy, având coordonatele (x,y) şi M ziduri sub forma unor segmente verticale având un capăt pe axa Ox şi o anumită înălţime fiecare. Vânătorul Elmer doreşte să împuşte cât mai multe raţe. El poate fi poziţionat în orice punct de abscisă număr natural nenul, pe axa Ox. O raţă poate fi ochită de vânător dacă zidul nu blochează glonţul vânătorului, adică segmentul imaginar delimitat de raţă şi de vânător nu se intersectează cu nici un zid.

Aici vânătorul poate ochi 4 raţe

Cerinţă

Să se afle numărul maxim de raţe care pot fi ochite de vânătorul Elmer.

Date de intrare

Fişierul de intrare elmer.in conţine p e prima linie numărul natural N, reprezentând numărul de raţe. Pe următoarele N linii se află perechi de numere naturale, reprezentând coordonatele raţelor. Pe următoarea linie se află numărul natural M, reprezentând numărul de ziduri, iar pe următoarele M linii, perechi de numere naturale, reprezentând abscisa şi înălţimea fiecărui zid.

Date de ieşire

Fişierul de ieşire elmer.out va conţine pe prima linie numărul maxim de raţe care pot fi ochite de Elmer.

Restricţii

  • 1 ≤ N, M ≤ 1 000
  • Coordonatele raţelor şi ale zidurilor, precum şi înălţimile zidurilor sunt din intervalul [1,1 000 000 000]
  • Se consideră numai coordonate întregi pozitive pentru vânător care nu corespund cu coordonatele niciunui zid.
  • Dacă glonţul trece prin vârful unui zid, se consideră că poate trece de el.
  • Se garantează că nu există ziduri cu aceeaşi abscisa, nici raţe aflate la aceleaşi coordonate şi nici raţe care să fie “în zid” (adică nici o raţă nu se afla pe segmentul închis delimitat de capetele unui zid).
  • Pentru 15% din teste, se garantează faptul că 1 ≤ N, M ≤ 50 şi vânătorului îi este suficient să se poziţioneze în intervalul [1,1 000] pentru a putea împuşca numărul maxim de raţe.
  • Pentru alte 25% din teste, se garantează doar faptul că 1 ≤ N, M ≤ 50.

Exemplu

elmer.inelmer.out
5
4 1
3 4
6 5
8 1
10 3
2
5 2
9 1
4
6
5 4
10 10
1 9
7 5
10 2
5 1
1
8 3
5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?