elmer

Elmer

== include(page="template/taskheader" task_id="elmer") ==

Poveste şi cerinţă...

Î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.
 
!problema/elmer?example.jpeg!
 
Aici vânătorul poate ochi 4 raţe
 
h2. Cerinţă
 
Să se afle numărul maxim de raţe care pot fi ochite de vânătorul Elmer.

h2. Date de intrare

Fişierul de intrare $elmer.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $elmer.out$ ...

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.

h2. 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$.

h2. Exemplu
table(example). |_. elmer.in |_. elmer.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|

 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="elmer") ==