Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- using namespace std;
- /*3. Se dau n intervale [a,b], a, b numere intregi. Sa se afiseze in fisierul intervale.out acele intervale
- care au proprietatea ca intersectia lor cu oricare dintre celelalte n-1 intervale este multimea vida si
- numarul acestor intervale. Fisierul de intrare intervale.in contine pe prima linie numarul n, iar pe
- urmatoarele n linii cate doua numere intregi, separate prin spatii, reprezentand capetele unui interval
- Ex: n=4 si intervalele [8,16] [17,20] [2,6] [10,15]
- -> 2 intervale [17,20] [2,6]
- */
- // !!!!! asta e doar o varianta de rezolvare, sigur exista mai multe optiuni
- ifstream fin("intervale.in");
- ofstream fout("intervale.out");
- int main()
- {
- //in vectorul a memoram capatul de inceput al fiecare interval (pe ex. dat, dupa citire, a va contine 8, 17, 2, 10)
- //in vectorul b memoram capatul de final al fiecarui interval (pe ex. dat, dupa citire, b va contine 16, 20, 6, 15)
- int n, i, j, a[100], b[100], k = 0, ok, v[100];
- fin >> n;
- for (i = 1; i <= n; i++)
- fin >> a[i] >> b[i];
- //matematic vorbind, un interval [a,b] intersecteaza [c,d] daca a < d si c < b
- //pentru intervalele [a[i],b[i]] si [a[j],b[j]] regula s-ar scrie a[i] < b[j] si a[j] < b[i]
- //parcurgem fiecare linie
- for (i = 1; i <= n; i++)
- {
- //pp ca nu intersecteaza alt interval citit
- ok = 0;
- //parcurgem din nou fiecare linie
- for (j = 1; j <= n; j++)
- //daca nu sunt pe aceeasi linie (nu intersectam intervalul curent cu el insusi)
- if (i != j)
- // verific conditia de intersectie de mai sus
- if (a[i] < b[j] && a[j] < b[i])
- //se intersecteaza
- ok = 1;
- //daca intervalul desemnat de linia i nu intersecteaza niciun alt interval, inserez linia intr-un vector (ca numar)
- if (ok == 0)
- {
- k++;
- v[k] = i;
- }
- }
- fout << k << endl;
- for (i = 1; i <= k; i++)
- //afisez a-ul si b-ul pentru liniile care au respectat cerinta
- fout << a[v[i]] << " " << b[v[i]] << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment