Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define all(v) (v).begin(),(v).end()
- int main() {
- int n;
- while (cin >> n) {
- if (n == 0) {
- cout << 0 << '\n';
- continue;
- }
- vector<int> x1(n), x2(n), y1(n), y2(n);
- vector<int> allx, ally;
- for (int i = 0; i < n; i++) {
- cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
- allx.push_back(x1[i]);
- allx.push_back(x2[i]);
- ally.push_back(y1[i]);
- ally.push_back(y2[i]);
- }
- sort(all(allx));
- sort(all(ally));
- allx.resize(unique(all(allx)) - allx.begin());
- ally.resize(unique(all(ally)) - ally.begin());
- int cntx = allx.size();
- int cnty = ally.size();
- vector<vector<int>> d(cntx + 1, vector<int>(cnty + 1));
- for (int i = 0; i < n; i++) {
- int i1 = lower_bound(all(allx), x1[i]) - allx.begin();
- int i2 = lower_bound(all(allx), x2[i]) - allx.begin();
- int j1 = lower_bound(all(ally), y1[i]) - ally.begin();
- int j2 = lower_bound(all(ally), y2[i]) - ally.begin();
- d[i1][j1]++;
- d[i1][j2]--;
- d[i2][j1]--;
- d[i2][j2]++;
- }
- for (int i = 0; i <= cntx; i++) {
- for (int j = 0; j <= cnty; j++) {
- if (i > 0)
- d[i][j] += d[i - 1][j];
- if (j > 0)
- d[i][j] += d[i][j - 1];
- if (i > 0 && j > 0)
- d[i][j] -= d[i - 1][j - 1];
- }
- }
- long long ans = 0;
- for (int i = 0; i < cntx; i++) {
- for (int j = 0; j < cnty; j++) {
- if (d[i][j] > 0) {
- long long dx = allx[i + 1] - allx[i];
- long long dy = ally[j + 1] - ally[j];
- ans += dx * dy;
- }
- }
- }
- cout << ans << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement