Problema 3.5

Precizare: Am modificat acest pastebin pe data de 26.11.2020 la ora 18:50 (înainte ca orice alt coleg să posteze vreo soluție alternativă) deoarece soluția precedentă nu trata corect anumite cazuri.

Idee de rezolvare:

Pentru a putea închide prima fereastră vom avea nevoie să închidem ferestrele care o acoperă, iar pentru a închide acele ferestre va trebui să închidem ferestrele care le acoperă la rândul lor șamd. Astfel, pentru a determina câte ferestre împiedică închiderea primei ferestre vom considera un graf orientat în care fiecare nod reprezintă o fereastră. Pe măsură ce citim coordonatele unei ferestre, verificăm dacă se intersectează cu cele anterior citite (verificăm dacă măcar un colț al unei ferestre se găsește în interiorul celeilalte sau invers) și dacă da, adăugăm un arc de la nodul precedent către cel abia citit. După citire, nodul x va duce către toate nodurile corespunzătoare ferestrelor ce trebuie închise exact cu un pas înainte de a închide fereastra x. În continuare, plecăm de la nodul 1 și „simulăm” închiderea ferestrelor printr-o parcurgere DFS recursivă cu condiția suplimentară că nodul adiacent lui x nu a fost închis încă (se poate verifica ușor folosind un vector caracteristic). Când un nod t nu mai are vecini sau toți vecinii acestuia au fost „închiși”, închidem și fereastra t și tot așa până ajungem la fereastra 1. De fiecare dată când închidem o fereastră incrementăm o variabilă (inițial egală cu 0), care va fi rezultatul final și pe care o vom afișa.

Pseudocod:

intersect(fereastră X, fereastră Y):
	dacă măcar un colț al ferestrei X se găsește în interiorul ferestrei Y:
		returnăm 1
	dacă măcar un colț al ferestrei Y se găsește în interiorul ferestrei X:
		returnăm 1
	returnăm 0

close(x):
	pentru fiecare y din lista lui x:
		dacă y nu a fost închis încă
			apelăm close(y)
	închidem fereastra y
	incrementăm numărul de ferestre închise

Do():
	citim n - numărul de ferestre
	pentru i de la 1 la n:
		citim pentru fiecare fereastră colțul stânga-jos și dreapta-sus
		generăm și celelalte 2 colțuri ale ferestrei
		pentru j de la i-1 la 1:
			dacă fereastra i se intersectează cu fereastra j:
				adăugăm în lista de adiacență a lui j pe nodul i
	apelăm închiderea ferestrei 1 prin funcția close(1)
	afișăm numărul de ferestre închise

Implementare C++: https://pastebin.com/x39rBTZQ

Complexitate timp: O(n^2)

Exemplele sunt cele date deja în enunțul problemei: https://pastebin.com/dewnan3G.