h2. Cerință
Se dau dimensiunile celor $N$ dreptunghiuri: $(A[i], B[i])$, unde $A[i]$ reprezintă lungimea dreptunghiului [$i$], iar $B[i]$ reprezintă lățimea acestuia.
Se dau dimensiunile celor $N$ dreptunghiuri: $(A[i], B[i])$, unde $A[i]$ reprezintă lungimea dreptunghiului [$i$], iar $B[i]$ reprezintă lățimea acestuia. Două dreptunghiuri $i$ și $j$ pot fi combinate dacă unul dintre acestea poate intra complet în celălalt. Mai precis, dacă $A[i] <= A[j]$ și $B[i] <= B[j]$ sau $A[j] <= A[i] și B[j] <= B[i]$. După combinare, dreptunghiul mai mic dispare.
Două dreptunghiuri $i$ și $j$ pot fi combinate dacă unul dintre acestea poate intra complet în celălalt. Mai precis, dacă $A[i] <= A[j] și B[i] <= B[j]$.
Gary are dreptul să aplice această operație de combinare de oricâte ori. Scopul lui este ca la final, numărul de dreptunghiuri rămase să fie minim. Să se găsească și să se afișeze acest număr.
h2. Date de intrare
Fișierul de intrare $drgary.in$ ...
Fișierul de intrare $drgary.in$ conține pe prima linie numărul natural [$N$], reprezentând numărul de dreptunghiuri. Fiecare din următoarele $N$ linii conține două numere naturale $A[i]$ și $B[i]$, reprezentând lungimea, respectiv lățimea dreptunghiului cu numărul [$i$].
h2. Date de ieșire
În fișierul de ieșire $drgary.out$ ...
În fișierul de ieșire $drgary.out$ se află un singur număr natural, reprezentând numărul minim de dreptunghiuri rămase după aplicarea operațiilor de combinare.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 50.000$
* $1 ≤ A[i], B[i] ≤ 10^9$
h2. Exemplu
table(example).
|_. drgary.in |_. drgary.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
2 1
2 2
1 2
1 3
| 2
|
h3. Explicație
...
Gary poate combina dreptunghiul $(2, 2)$ cu $(2, 1)$ și dreptunghiul $(1, 2)$ cu $(1, 3)$. La final, vor rămâne două dreptunghiuri: $(2, 2)$ și $(1, 3)$.
== include(page="template/taskfooter" task_id="drgary") ==
