Cod sursa(job #2636050)

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

using namespace std;

constexpr int base = 97, MOD = 93939;

int N, M, W, H;

vector <pair <int, int> > Hash[MOD+1];

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

namespace InParser
{
static const int BSIZE = (1 << 16);

static int pos = BSIZE - 1;
static char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}

inline int Int ()
{
    int ans = 0, sign = 1;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch == '-')
        {
            sign = -1;

            break;
        }

        if(Ch >= '0' && Ch <= '9')
        {
            ans = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            ans = ans * 10 + (int)(Ch - '0');
        else
            break;
    }

    return (ans * sign);
}
};


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

    N = InParser :: Int();
    M = InParser :: Int();
    W = InParser :: Int();
    H = InParser :: Int();

    for (int i = 1; i <= N; ++ i ) {
        int x, y;
        x = InParser :: Int(), y = InParser :: Int();
        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;
        x = InParser :: Int(), y = InParser :: Int();
        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;
}