Fișierul intrare/ieșire	drgary.in, drgary.out	Sursă	Concurs clasa a 9-a
Autor	Teodor Plop	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.05 sec	Limită de memorie	1024 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Dreptunghiurile lui Gary (clasa a 9-a)

Era dimineață, iar Gary se pregătea de înfruntarea cu strigoiul care de luni bune tot dădea tărcoale castelului abandonat de la marginea Vizimei. Și cum se putea pregăti mai bine decât culegând rostopască pentru a își aproviziona stocul de poțiuni? Umblând așa prin pădure la cules de plante și mure, a fost întrerupt în mare grabă de un comerciant:

- Maestre Gary, am o treabă pe care doar un vânător o poate rezolva! Am N plăci dreptunghiuri și trebuie să le combin pe toate înainte de a le vinde!

Deși nu se abate prea des din calea destinului, Gary a ales să îl ajute pe negustor cu această problemă de importanță globală.

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.

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.

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.

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.

Restricții

• 1 ≤ N ≤ 50.000
• 1 ≤ A[i], B[i] ≤ 10^9

Exemplu

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).