Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define MAX 1005
  7. int n, m, k;
  8. vector<pair<int, int> > V;
  9. vector<int> X;
  10. vector<int> Y;
  11. map<int, int> mpX, mpY;
  12. map<int, int> revX, revY;
  13. int grid[MAX][MAX];
  14. bool vis[MAX][MAX];
  15.  
  16. int calcVer(int x1, int x2)
  17. {
  18. if(x1 == 0 || x2 == 0) return 0;
  19. int p = revX[x1];
  20. int q = revX[x2];
  21. return abs(p-q);
  22. }
  23.  
  24. int calcHor(int y1, int y2)
  25. {
  26. if(y1 == 0 || y2 == 0) return 0;
  27. int p = revY[y1];
  28. int q = revY[y2];
  29. return abs(p-q);
  30. }
  31.  
  32. int calcAll(int x1, int y1, int x2, int y2)
  33. {
  34. if(x1 == 0 || y1 == 0 || x2 == 0 || y2 == 0) return 0;
  35. x1 = revX[x1];
  36. x2 = revX[x2];
  37. y1 = revY[y1];
  38. y2 = revY[y2];
  39. return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
  40. }
  41.  
  42. int main()
  43. {
  44. int cases;
  45. scanf("%d", &cases);
  46. while(cases--){
  47. scanf("%d %d %d", &n, &m, &k);
  48. for(int i=0; i<k; i++){
  49. int x, y;
  50. scanf("%d %d", &x, &y);
  51. V.push_back(make_pair(x, y));
  52. X.push_back(x);
  53. Y.push_back(y);
  54. }
  55. sort(X.begin(), X.end());
  56. sort(Y.begin(), Y.end());
  57. int idx = 0;
  58. for(int i=0; i<X.size(); i++){
  59. int v = X[i];
  60. if(mpX[v] == 0){
  61. idx++;
  62. mpX[v] = idx;
  63. revX[idx] = v;
  64. }
  65. }
  66. int idy = 0;
  67. for(int i=0; i<Y.size(); i++){
  68. int v = Y[i];
  69. if(mpY[v] == 0){
  70. idy++;
  71. mpY[v] = idy;
  72. revY[idy] = v;
  73. }
  74. }
  75. memset(grid, 0, sizeof grid);
  76. memset(vis, false, sizeof vis);
  77. for(int i=0; i<k; i++){
  78. int x = V[i].first;
  79. int y = V[i].second;
  80. x = mpX[x];
  81. y = mpY[y];
  82. vis[x][y] = true;
  83. grid[x][y] = 1;
  84. }
  85. long long odd = 0, even = 0;
  86. for(int i=1; i<=idx; i++){
  87. for(int j=1; j<=idy; j++){
  88. int cur = i*j;
  89. cur = cur%2;
  90. if(cur) odd++;
  91. else even++;
  92.  
  93. if(cur == 1){
  94. even += calcAll(i, j, i-1, j-1);
  95. }
  96. else {
  97. odd += calcAll(i, j, i-1, j-1);
  98. }
  99. cur = (i-1)*j;
  100. cur = cur%2;
  101. if(cur == 1){
  102. odd += calcVer(i, i-1);
  103. }
  104. else {
  105. even += calcVer(i, i-1);
  106. }
  107. cur = i*(j-1);
  108. if(cur == 1){
  109. odd += calcHor(j, j-1);
  110. }
  111. else {
  112. even += calcHor(j, j-1);
  113. }
  114. }
  115. }
  116. if(idx == 0) idx = 1;
  117. if(idy == 0) idy = 1;
  118. cout << odd << " " << even << endl;
  119. int tot = idx*idy;
  120. tot = tot%2;
  121. int sum = (n-idx+1)*(m-idy+1);
  122. sum = sum-1;
  123. if(tot == 0) even += sum;
  124. else odd += sum;
  125. cout << odd << " " << even << endl;
  126. }
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement