Advertisement
Josif_tepe

Untitled

Jan 27th, 2024
496
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. bool dali_ke_se_zalepi(int platforma_L, int platforma_R, int otsecka_L, int otsecka_R) {
  6.    
  7.     if(otsecka_R < platforma_L or platforma_R < otsecka_L) {
  8.         return false;
  9.     }
  10.     if(otsecka_L < platforma_L and platforma_R < otsecka_R) {
  11.         return false;
  12.     }
  13.    
  14.     if(platforma_L <= otsecka_L and otsecka_R <= platforma_R) {
  15.         return true;
  16.     }
  17.     if(otsecka_L < platforma_L) {
  18.         if(otsecka_R - platforma_L >= platforma_L - otsecka_L) {
  19.             return true;
  20.         }
  21.         else {
  22.             return false;
  23.         }
  24.     }
  25.     else {
  26.         if(platforma_R - otsecka_L >= otsecka_R - platforma_R) {
  27.             return true;
  28.         }
  29.         else {
  30.             return false;
  31.         }
  32.     }
  33.    
  34.     return false;
  35. }
  36. int main()
  37. {
  38.     int n, L;
  39.     cin >> n >> L;
  40.    
  41.     vector<pair<int, int> > otsecki;
  42.     for(int i = 0; i < n; i++) {
  43.         int a, b;
  44.         cin >> a >> b;
  45.         otsecki.push_back(make_pair(a, b));
  46.     }
  47.     int platforma_L = 0, platforma_R = L;
  48.     vector<bool> iskoristeno(n, false);
  49.     int cnt = 0;
  50.     cout << endl;
  51.     for(int i = 0; i < n; i++) {
  52.         for(int j = 0; j < n; j++) {
  53.             if(!iskoristeno[j]) {
  54.                 if(dali_ke_se_zalepi(platforma_L, platforma_R, otsecki[j].first, otsecki[j].second)) {
  55.                     iskoristeno[j] = true;
  56.                     platforma_L = min(platforma_L, otsecki[j].first);
  57.                     platforma_R = max(platforma_R, otsecki[j].second);
  58.                     cnt++;
  59.                 }
  60.             }
  61.         }
  62.        
  63.     }
  64.     cout << cnt << endl;
  65.     return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement