Advertisement
Guest User

Untitled

a guest
Oct 17th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(v) (v).begin(),(v).end()
  4.  
  5. int main() {
  6.     int n;
  7.     while (cin >> n) {
  8.         if (n == 0) {
  9.             cout << 0 << '\n';
  10.             continue;
  11.         }
  12.         vector<int> x1(n), x2(n), y1(n), y2(n);
  13.         vector<int> allx, ally;
  14.         for (int i = 0; i < n; i++) {
  15.             cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
  16.             allx.push_back(x1[i]);
  17.             allx.push_back(x2[i]);
  18.             ally.push_back(y1[i]);
  19.             ally.push_back(y2[i]);
  20.         }
  21.         sort(all(allx));
  22.         sort(all(ally));
  23.         allx.resize(unique(all(allx)) - allx.begin());
  24.         ally.resize(unique(all(ally)) - ally.begin());
  25.         int cntx = allx.size();
  26.         int cnty = ally.size();
  27.         vector<vector<int>> d(cntx + 1, vector<int>(cnty + 1));
  28.         for (int i = 0; i < n; i++) {
  29.             int i1 = lower_bound(all(allx), x1[i]) - allx.begin();
  30.             int i2 = lower_bound(all(allx), x2[i]) - allx.begin();
  31.             int j1 = lower_bound(all(ally), y1[i]) - ally.begin();
  32.             int j2 = lower_bound(all(ally), y2[i]) - ally.begin();
  33.             d[i1][j1]++;
  34.             d[i1][j2]--;
  35.             d[i2][j1]--;
  36.             d[i2][j2]++;
  37.         }
  38.         for (int i = 0; i <= cntx; i++) {
  39.             for (int j = 0; j <= cnty; j++) {
  40.                 if (i > 0)
  41.                     d[i][j] += d[i - 1][j];
  42.                 if (j > 0)
  43.                     d[i][j] += d[i][j - 1];
  44.                 if (i > 0 && j > 0)
  45.                     d[i][j] -= d[i - 1][j - 1];
  46.             }
  47.         }
  48.         long long ans = 0;
  49.         for (int i = 0; i < cntx; i++) {
  50.             for (int j = 0; j < cnty; j++) {
  51.                 if (d[i][j] > 0) {
  52.                     long long dx = allx[i + 1] - allx[i];
  53.                     long long dy = ally[j + 1] - ally[j];
  54.                     ans += dx * dy;
  55.                 }
  56.             }
  57.         }
  58.         cout << ans << '\n';
  59.     }
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement