Advertisement
Guest User

Untitled

a guest
Apr 19th, 2016
163
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. #include <set>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. /*
  8. Note for reading ugly variable names more easily:
  9. kx stands for "small x" i.e. the left side,
  10. nx stands for "large x" i.e. the right side
  11. and ky and ny are similarly the bottom and top.
  12. (Abbreviated in Hungarian, my native language...)
  13. */
  14.  
  15. int N;
  16.  
  17. vector<int> X;
  18. vector<int> Y;
  19.  
  20. struct Rect
  21. {
  22.     int kx, ky, nx, ny;
  23. };
  24.  
  25. Rect R[1000];
  26.  
  27. int main()
  28. {
  29.     ios::sync_with_stdio(false);
  30.     cin >> N;
  31.     set<int> sx;
  32.     set<int> sy;
  33.     for (int i = 0; i < N; i++)
  34.     {
  35.         cin >> R[i].kx >> R[i].ny >> R[i].nx >> R[i].ky;
  36.         sx.insert(R[i].kx); sx.insert(R[i].nx);
  37.         sy.insert(R[i].ky); sy.insert(R[i].ny);
  38.     }
  39.     for (int x : sx)
  40.     {
  41.         X.push_back(x);
  42.     }
  43.     for (int y : sy)
  44.     {
  45.         Y.push_back(y);
  46.     }
  47.     bool M[X.size()-1][Y.size()-1];
  48.     for (int i = 0; i < X.size()-1; i++)
  49.         for (int j = 0; j < Y.size()-1; j++)
  50.             M[i][j] = false;
  51.     long long S = 0;
  52.     for (Rect r : R)
  53.     {
  54.         int ki = (lower_bound(X.begin(), X.end(), r.kx) - X.begin());
  55.         int ni = (lower_bound(X.begin(), X.end(), r.nx) - X.begin());
  56.         int kj = (lower_bound(Y.begin(), Y.end(), r.ky) - Y.begin());
  57.         int nj = (lower_bound(Y.begin(), Y.end(), r.ny) - Y.begin());
  58.         for (int i = ki; i < ni; i++)
  59.         {
  60.             for (int j = kj; j < nj; j++)
  61.             {
  62.                 if (!M[i][j])
  63.                 {
  64.                     M[i][j] = true;
  65.                     S += ((long long)(X[i+1]-X[i]))*(Y[j+1]-Y[j]);
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     cout << S << endl;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement