ograzi

Ograzi

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

Ciobanasul Ion are m oi punctiforme si n ograzi dreptunghiulare. Fiecare ograda de dimensiune HxW, aliniata cu axele de coordonate. Ograzile sunt complet disjuncte, si gardurile lor nu se suprapun. Pe Ion il intereseaza cate oi sunt in interiorul vreunei ograzi.

Ciobanasul Ion are $M$ oi punctiforme si $N$ ograzi dreptunghiulare. Fiecare ograda are dimensiunile $W x H$ (latime $W$ si inaltime $H$) si este aliniata cu axele de coordonate. Ograzile sunt complet disjuncte, si gardurile lor nu se suprapun. Pe Ion il intereseaza cate oi sunt in interiorul tuturor ograzilor.

h2. Date de intrare

Dreptunghiurile se dau prin coordonatele coltul lor de stanga sus. Coordonatele oilor se genereaza prin urmatorul algoritm.

Pe prima linie din fisierul de intrare $ograzi.in$ se gasesc numerele naturale $N M W H$ separate prin spatii. Urmatoarele $N$ contin perechi de numere naturale $x y$ reprezentand coltul stanga-jos al unui dreptunghi. Urmatoarele $M$ linii contin perechi de numere naturale $x y$ reprezetand locul unei oi.

h2. Date de iesire

Numarul oilor continute in un dreptunghi.

Fisierul de iesire $ograzi.out$ va contine un singur numar natural reprezentand numarul de oi care sunt in interiorul tuturor ograzilor.

h2. Restrictii

* $... ≤ ... ≤ ...$
 
1 <= N <= 50.000
1 <= M <= 1.000.000

* $1 ≤ N ≤ 50.000$
* $1 ≤ M ≤ 100.000$
* $1 ≤ W, H ≤ 10^6^$
* Coordonatele oilor si ale colturilor dreptunghiurilor sunt in intervalul $[0...10^6^]$
* O oaie aflata pe marginea unei ograde se considera in interior
* Pot fi mai multe oi in aceeasi pozitie
* Datorita volumului mare de date de intrare se recomanda citirea datelor folosind functii precum $fgets$

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

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

| 3 4 3 2
2 2
4 6
6 1
4 3
5 7
9 4
8 9
| 2 |

h3. Explicatie

...

!problema/ograzi?ograzi.jpg!

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

1649