Advertisement
KinDeR___

Untitled

Oct 14th, 2023
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.13 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define isz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define ll long long
  6. #define pii pair<int,int>
  7. #define fi first
  8. #define se second
  9. #define isz(x) int(x.size())
  10. #define ull unsigned long long
  11. #define vi vector<int>
  12. #define vll vector<ll>
  13. #define vch vector<char>
  14. #define vvch vector<vch>
  15. #define vvi vector<vector<int>>
  16. #define vvvi vector<vvi>
  17. #define vvll vector<vector<ll>>
  18. #define vpii vector<pair<int,int>>
  19. #define vvpii vector<vpii>
  20. #define forn(i,n) for(int i=0;i<(int)n;++i)
  21. #define pb push_back
  22.  
  23. using namespace std;
  24.  
  25. const int UNDEF = -1;
  26. const int MOD = 1e9 + 7;
  27. const int INF = 1e9;
  28.  
  29. struct Square {
  30. int lx, ly, rx, ry;
  31. Square(const int& lx, const int& ly, const int& rx, const int& ry)
  32. : lx(lx)
  33. , ly(ly)
  34. , rx(rx)
  35. , ry(ry)
  36. {}
  37. };
  38.  
  39. int main() {
  40.  
  41. ios::sync_with_stdio(false);
  42. cin.tie(nullptr);
  43. freopen("input.txt", "rt", stdin);
  44. freopen("output.txt", "wt", stdout);
  45.  
  46. int N, A, K; // N - n_knight | A - width square | K-max_step;
  47. cin >> N >> A >> K;
  48.  
  49. vi all_x, all_y;
  50. vi knight_x(N), knight_y(N);
  51. vector<Square> knight_sq;
  52.  
  53. for (int i = 0; i < N; ++i) {
  54. cin >> knight_x[i] >> knight_y[i];
  55.  
  56. all_x.pb(knight_x[i]);
  57. all_y.pb(knight_y[i]);
  58.  
  59. int lx = max(1, knight_x[i] - K), ly = max(1, knight_y[i] - K),
  60. rx = min(A, knight_x[i] + K), ry = min(A, knight_y[i] + K);
  61.  
  62. all_x.pb(lx);
  63. all_x.pb(rx);
  64.  
  65. all_y.pb(ly);
  66. all_y.pb(ry);
  67.  
  68. knight_sq.pb(Square(lx, ly, rx, ry));
  69.  
  70. }
  71.  
  72. sort(all(all_x));
  73. sort(all(all_y));
  74.  
  75. all_x.erase(unique(all(all_x)), all_x.end());
  76. all_y.erase(unique(all(all_y)), all_y.end());
  77.  
  78. set<pii> was;
  79.  
  80. for (int i = 0; i < N; ++i) {
  81.  
  82. knight_x[i] = int(lower_bound(all(all_x), knight_x[i]) - all_x.begin());
  83. knight_y[i] = int(lower_bound(all(all_y), knight_y[i]) - all_y.begin());
  84.  
  85. was.insert({ knight_x[i],knight_y[i] });
  86.  
  87. knight_sq[i].lx = int(lower_bound(all(all_x), knight_sq[i].lx) - all_x.begin());
  88. knight_sq[i].rx = int(lower_bound(all(all_x), knight_sq[i].rx) - all_x.begin());
  89.  
  90. knight_sq[i].ly = int(lower_bound(all(all_y), knight_sq[i].ly) - all_y.begin());
  91. knight_sq[i].ry = int(lower_bound(all(all_y), knight_sq[i].ry) - all_y.begin());
  92. }
  93.  
  94. int sizeX = isz(all_x), sizeY = isz(all_y);
  95.  
  96. vvi preff(1 + sizeX, vi(1 + sizeY, 0));
  97.  
  98. for (int x = 1; x <= sizeX; ++x) {
  99. for (int y = 1; y <= sizeY; ++y) {
  100. preff[x][y] = preff[x][y - 1] + preff[x - 1][y] - preff[x - 1][y - 1];
  101. if (was.count({ x - 1,y - 1 }) > 0) preff[x][y]++;
  102. }
  103. }
  104.  
  105. function<int(int, int, int, int)> GetSum = [&](int lx, int ly, int rx, int ry) {
  106. return preff[rx + 1][ry + 1] - preff[rx + 1][ly] - preff[lx][ry + 1] + preff[lx][ly];
  107. };
  108.  
  109. int ans = 0;
  110. for (int i = 0; i < N; ++i) {
  111. for (int j = i + 1; j < N; ++j) {
  112. if (knight_sq[i].lx <= knight_x[j] && knight_x[j] <= knight_sq[i].rx
  113. && knight_sq[i].ly <= knight_y[j] && knight_y[j] <= knight_sq[i].ry) {
  114.  
  115. int lX = max(knight_sq[i].lx, knight_sq[j].lx);
  116. int rX = min(knight_sq[i].rx, knight_sq[j].rx);
  117. int lY = max(knight_sq[i].ly, knight_sq[j].ly);
  118. int rY = min(knight_sq[i].ry, knight_sq[j].ry);
  119. if (lX <= rX && lY <= rY) {
  120. //int s = GetSum(lX, lY, rX, rY);
  121. int s=preff[rX + 1][rY + 1] - preff[rX + 1][lY] - preff[lX][rY + 1] + preff[lX][lY];
  122. if (lX <= knight_x[i] && knight_x[i] <= rX &&
  123. lY <= knight_y[i] && knight_y[i] <= rY) {
  124. s--;
  125. }
  126. if (lX <= knight_x[j] && knight_x[j] <= rX &&
  127. lY <= knight_y[j] && knight_y[j] <= rY) {
  128. s--;
  129. }
  130. ans += s;
  131. }
  132. }
  133. }
  134. }
  135.  
  136. cout << ans / 3;
  137.  
  138.  
  139. return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement