fork(11) download
copy 
  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) d[i][j] += d[i - 1][j];
  41. 				if (j > 0) d[i][j] += d[i][j - 1];
  42. 				if (i > 0 && j > 0) d[i][j] -= d[i - 1][j - 1];
  43. 			}
  44. 		}
  45. 		long long ans = 0;
  46. 		for (int i = 0; i < cntx; i++) {
  47. 			for (int j = 0; j < cnty; j++) {
  48. 				if (d[i][j] > 0) {
  49. 					long long dx = allx[i + 1] - allx[i];
  50. 					long long dy = ally[j + 1] - ally[j];
  51. 					ans += dx * dy;
  52. 				}
  53. 			}
  54. 		}
  55. 		cout << ans << '\n';
  56. 	}
  57. }
  58.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
3
1 1 3 5
5 2 7 4
2 4 6 7
2
0 0 2 2
1 3 2 4
stdout
copy 
23
5
https://ideone.com/d0bRIg
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!