ioana_martin98

Untitled

May 3rd, 2022
1,145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <fstream>
  2. using namespace std;
  3. /*3. Se dau n intervale [a,b], a, b numere intregi. Sa se afiseze in fisierul intervale.out acele intervale
  4.     care au proprietatea ca intersectia lor cu oricare dintre celelalte n-1 intervale este multimea vida si
  5.     numarul acestor intervale. Fisierul de intrare intervale.in contine pe prima linie numarul n, iar pe
  6.     urmatoarele n linii cate doua numere intregi, separate prin spatii, reprezentand capetele unui interval
  7.     Ex: n=4 si intervalele [8,16] [17,20] [2,6] [10,15]
  8.     -> 2 intervale [17,20] [2,6]
  9. */
  10.  
  11. // !!!!! asta e doar o varianta de rezolvare, sigur exista mai multe optiuni
  12. ifstream fin("intervale.in");
  13. ofstream fout("intervale.out");
  14.  
  15. int main()
  16. {
  17.     //in vectorul a memoram capatul de inceput al fiecare interval (pe ex. dat, dupa citire, a va contine 8, 17, 2, 10)
  18.     //in vectorul b memoram capatul de final al fiecarui interval (pe ex. dat, dupa citire, b va contine 16, 20, 6, 15)
  19.     int n, i, j, a[100], b[100], k = 0, ok, v[100];
  20.     fin >> n;
  21.     for (i = 1; i <= n; i++)
  22.         fin >> a[i] >> b[i];
  23.  
  24.     //matematic vorbind, un interval [a,b] intersecteaza [c,d] daca a < d  si c < b
  25.     //pentru intervalele [a[i],b[i]] si [a[j],b[j]] regula s-ar scrie a[i] < b[j] si a[j] < b[i]
  26.     //parcurgem fiecare linie
  27.     for (i = 1; i <= n; i++)
  28.     {
  29.         //pp ca nu intersecteaza alt interval citit
  30.         ok = 0;
  31.         //parcurgem din nou fiecare linie
  32.         for (j = 1; j <= n; j++)
  33.             //daca nu sunt pe aceeasi linie (nu intersectam intervalul curent cu el insusi)
  34.             if (i != j)
  35.                 // verific conditia de intersectie de mai sus
  36.                 if (a[i] < b[j] && a[j] < b[i])
  37.                     //se intersecteaza
  38.                     ok = 1;
  39.         //daca intervalul desemnat de linia i nu intersecteaza niciun alt interval, inserez linia intr-un vector (ca numar)
  40.         if (ok == 0)
  41.         {
  42.             k++;
  43.             v[k] = i;
  44.         }
  45.     }
  46.     fout << k << endl;
  47.     for (i = 1; i <= k; i++)
  48.         //afisez a-ul si b-ul pentru liniile care au respectat cerinta
  49.         fout << a[v[i]] << " " << b[v[i]] << endl;
  50.  
  51.     return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment