Vừa đọc cái ebook về interval tree của vnoi (link: vnoi.info/index.php?option=com_docman&task=doc_download&gid= 62&Itemid=27) và áp dụng sang C++. Đây là code:
C++ Code:
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4.  
  5. struct mlab {
  6.     int Hdo;
  7.     int Lo, Hi;
  8.     bool Op;
  9. } Label[100];
  10.  
  11. float mmin = 20000.0f, mmax = -20000.0f, area;
  12. int num[100];   float cov[100];
  13.  
  14. bool comp(const mlab& a, const mlab& b )
  15. {
  16.     return a.Hdo < b.Hdo;
  17. }
  18.  
  19. void OpenT(float a, float b, int k, int lo, int hi)
  20. {
  21.     if (a+1 >= b)
  22.     {
  23.         if (lo <= a && b <= hi)
  24.             cov[k] = 1;
  25.         else cov[k] = 0;
  26.         return;
  27.     }
  28.     if (lo <= a && b <= hi)
  29.     {
  30.         num[k]++;
  31.         cov[k] = b-a;
  32.         return;
  33.     }
  34.     if (hi <= a || b <= lo)
  35.         return;
  36.     OpenT(a, (a+b)/2, 2*k+1, lo, hi);
  37.     OpenT((a+b)/2, a, 2*k+2, lo, hi);
  38.  
  39.     if (num[k] == 0)
  40.         cov[k] = cov[k*2+1] + cov[k*2+2];
  41. }
  42.  
  43. void OpenF(float a, float b, int k, int lo, int hi)
  44. {
  45.     if (a+1 >= b)
  46.     {
  47.         if (lo <= a && b <= hi)
  48.         {
  49.             num[k]--;
  50.             if (cov[k] == 0)
  51.                 cov[k] = cov[k*2+1] + cov[k*2+2];
  52.         }
  53.         return;
  54.     }
  55.     if (lo <= a && b <= hi)
  56.     {
  57.         num[k]--;
  58.         if (cov[k] == 0)
  59.             cov[k] = cov[k*2+1] + cov[k*2+2];
  60.         return;
  61.     }
  62.     if (hi <= a || b <= lo)
  63.         return;
  64.     OpenF(a, (a+b)/2, 2*k+1, lo, hi);
  65.     OpenF((a+b)/2, a, 2*k+2, lo, hi);
  66.    
  67.     if (num[k] == 0)
  68.         cov[k] = cov[k*2+1] + cov[k*2+2];
  69. }
  70.  
  71. int main()
  72. {
  73.     ifstream ipf("cover.txt");
  74.     if (!ipf)   return 0;
  75.     int n, i, t;
  76.     int x, y, z, u;
  77.     ipf >> n;
  78.  
  79.     fill(num, num+100, 0);
  80.     fill(cov, cov+100, 0);
  81.    
  82.     i = 0;
  83.     for (t = 0; t < n; t++)
  84.     {
  85.         ipf >> x >> y >> z >> u;
  86.         Label[i].Hdo = x;   Label[i+1].Hdo = z;
  87.         Label[i].Hi = Label[i+1].Hi = y;
  88.         Label[i].Lo = Label[i+1].Lo = u;
  89.         Label[i].Op = true;
  90.         Label[i+1].Op = false;
  91.         i += 2;
  92.        
  93.         mmax = mmax<y?y : mmax;
  94.         mmin = mmin>u?u : mmin;
  95.     }
  96.  
  97.     //Tinh toan
  98.     sort(Label, Label+2*n, comp);
  99.  
  100.     OpenT(mmin, mmax, 0, Label[0].Lo, Label[0].Hi);
  101.     area = 0;
  102.    
  103.     for (i = 1; i < 2*n; ++i)
  104.     {
  105.         area += cov[0]*(Label[i].Hdo - Label[i-1].Hdo);
  106.         if (Label[i].Op)
  107.             OpenT(mmin, mmax, 0, Label[i].Lo, Label[i].Hi);
  108.         else OpenF(mmin, mmax, 0, Label[i].Lo, Label[i].Hi);
  109.     }
  110.    
  111.     cout << area;
  112.  
  113.     return 0;
  114. }
Kết quả bị sai. Giúp .
Đây là file test:
C++ Code:
  1. 5
  2. -2  2  1  0
  3.  4  2  6  0
  4. -1  5  3  2
  5.  4  6  6  5
  6.  2  3  5  1
KQ: 28 (dvdt)