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. 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.
Se dau dimensiunile celor $N$ dreptunghiuri: $(A[i], B[i])$, unde $A[i]$ reprezintă lungimea dreptunghiului [$i$], iar $B[i]$ reprezintă lățimea acestuia.
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.
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]$.
h2. Date de intrare
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$].
Fișierul de intrare $drgary.in$ ...
h2. Date de ieșire
Î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.
În fișierul de ieșire $drgary.out$ ...
h2. Restricții
* $1 ≤ N ≤ 50.000$
* $1 ≤ A[i], B[i] ≤ 10^9$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. drgary.in |_. drgary.out |
| 4
2 1
2 2
1 2
1 3
| 2
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
