Cod sursa(job #2636048)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 16 iulie 2020 13:31:08
Problema Ograzi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>

using namespace std;

constexpr int bsize = (1<<16);
constexpr int base = 97, MOD = 93939;
constexpr int XYMAX = 1e6 + 5;

int N, M, W, H;

vector <pair <int, int> > Hash[XYMAX];

char ch[ bsize ];
int pos = 0;

int dx[4] = {0, 0, -1, -1};
int dy[4] = {0, -1, -1, 0};

void read (int &x) {
    x = 0;

    while (!isdigit(ch[ pos ])) {
        ++ pos;

        if (pos == bsize) {
            pos = 0;
            fread(ch, 1, bsize, stdin);
        }
    }

    while (isdigit(ch[ pos ])) {
        x = x * 10 + (ch[ pos ] - '0');
        ++ pos;

        if (pos == bsize) {
            pos = 0;
            fread(ch, 1, bsize, stdin);
        }
    }
}

void Citire () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    fread(ch, 1, bsize, stdin);

    read(N);
    read(M);
    read(W);
    read(H);

    for (int i = 1; i <= N; ++ i ) {
        int x, y; read(x), read(y);
        int cod_x = x / W, cod_y = y / H;

        int val = (cod_x * base + cod_y) % MOD;

        Hash[ val ].push_back({x, y});
    }
}

bool Interior (pair <int, int> p, pair <int, int> dr) {
    return (dr.first <= p.first && p.first <= dr.first + W && dr.second <= p.second && p.second <= dr.second + H);
}

void Solutie () {
    int sol = 0;
    for (int i = 1; i <= M; ++ i ) {
        int x, y; read(x), read(y);
        int cod_x = x / W, cod_y = y / H;

        for (int dir = 0; dir < 4; ++ dir ) {
            int dr_x = cod_x + dx[ dir ];
            int dr_y = cod_y + dy[ dir ];

            if (dr_x < 0 || dr_y < 0) continue;

            int val = (dr_x * base + dr_y) % MOD;
            bool ok = false;

            for (int j = 0; j < Hash[val].size(); ++ j ) {
                if (Interior({x, y}, {Hash[val][j].first, Hash[val][j].second})) ok = 1;
            }

            if (ok == true) {
                ++ sol;
                break;
            }
        }
    }

    cout << sol << '\n';
}

int main()
{
    Citire ();

    Solutie ();


    return 0;
}