Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define isz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define ll long long
- #define pii pair<int,int>
- #define fi first
- #define se second
- #define isz(x) int(x.size())
- #define ull unsigned long long
- #define vi vector<int>
- #define vll vector<ll>
- #define vch vector<char>
- #define vvch vector<vch>
- #define vvi vector<vector<int>>
- #define vvvi vector<vvi>
- #define vvll vector<vector<ll>>
- #define vpii vector<pair<int,int>>
- #define vvpii vector<vpii>
- #define forn(i,n) for(int i=0;i<(int)n;++i)
- #define pb push_back
- using namespace std;
- const int UNDEF = -1;
- const int MOD = 1e9 + 7;
- const int INF = 1e9;
- struct Square {
- int lx, ly, rx, ry;
- Square(const int& lx, const int& ly, const int& rx, const int& ry)
- : lx(lx)
- , ly(ly)
- , rx(rx)
- , ry(ry)
- {}
- };
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- int N, A, K; // N - n_knight | A - width square | K-max_step;
- cin >> N >> A >> K;
- vi all_x, all_y;
- vi knight_x(N), knight_y(N);
- vector<Square> knight_sq;
- for (int i = 0; i < N; ++i) {
- cin >> knight_x[i] >> knight_y[i];
- all_x.pb(knight_x[i]);
- all_y.pb(knight_y[i]);
- int lx = max(1, knight_x[i] - K), ly = max(1, knight_y[i] - K),
- rx = min(A, knight_x[i] + K), ry = min(A, knight_y[i] + K);
- all_x.pb(lx);
- all_x.pb(rx);
- all_y.pb(ly);
- all_y.pb(ry);
- knight_sq.pb(Square(lx, ly, rx, ry));
- }
- sort(all(all_x));
- sort(all(all_y));
- all_x.erase(unique(all(all_x)), all_x.end());
- all_y.erase(unique(all(all_y)), all_y.end());
- set<pii> was;
- for (int i = 0; i < N; ++i) {
- knight_x[i] = int(lower_bound(all(all_x), knight_x[i]) - all_x.begin());
- knight_y[i] = int(lower_bound(all(all_y), knight_y[i]) - all_y.begin());
- was.insert({ knight_x[i],knight_y[i] });
- knight_sq[i].lx = int(lower_bound(all(all_x), knight_sq[i].lx) - all_x.begin());
- knight_sq[i].rx = int(lower_bound(all(all_x), knight_sq[i].rx) - all_x.begin());
- knight_sq[i].ly = int(lower_bound(all(all_y), knight_sq[i].ly) - all_y.begin());
- knight_sq[i].ry = int(lower_bound(all(all_y), knight_sq[i].ry) - all_y.begin());
- }
- int sizeX = isz(all_x), sizeY = isz(all_y);
- vvi preff(1 + sizeX, vi(1 + sizeY, 0));
- for (int x = 1; x <= sizeX; ++x) {
- for (int y = 1; y <= sizeY; ++y) {
- preff[x][y] = preff[x][y - 1] + preff[x - 1][y] - preff[x - 1][y - 1];
- if (was.count({ x - 1,y - 1 }) > 0) preff[x][y]++;
- }
- }
- function<int(int, int, int, int)> GetSum = [&](int lx, int ly, int rx, int ry) {
- return preff[rx + 1][ry + 1] - preff[rx + 1][ly] - preff[lx][ry + 1] + preff[lx][ly];
- };
- int ans = 0;
- for (int i = 0; i < N; ++i) {
- for (int j = i + 1; j < N; ++j) {
- if (knight_sq[i].lx <= knight_x[j] && knight_x[j] <= knight_sq[i].rx
- && knight_sq[i].ly <= knight_y[j] && knight_y[j] <= knight_sq[i].ry) {
- int lX = max(knight_sq[i].lx, knight_sq[j].lx);
- int rX = min(knight_sq[i].rx, knight_sq[j].rx);
- int lY = max(knight_sq[i].ly, knight_sq[j].ly);
- int rY = min(knight_sq[i].ry, knight_sq[j].ry);
- if (lX <= rX && lY <= rY) {
- //int s = GetSum(lX, lY, rX, rY);
- int s=preff[rX + 1][rY + 1] - preff[rX + 1][lY] - preff[lX][rY + 1] + preff[lX][lY];
- if (lX <= knight_x[i] && knight_x[i] <= rX &&
- lY <= knight_y[i] && knight_y[i] <= rY) {
- s--;
- }
- if (lX <= knight_x[j] && knight_x[j] <= rX &&
- lY <= knight_y[j] && knight_y[j] <= rY) {
- s--;
- }
- ans += s;
- }
- }
- }
- }
- cout << ans / 3;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement