Cod sursa(job #2634967)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 12 iulie 2020 20:12:54
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef pair < int, int > PII;

const int NMAX = 5e4 + 5, MMAX = 1e5 + 5;
const int Base = 1e6 + 3, Mod = 666013;

int N, M, W, H;

vector < PII > Hash[Mod];

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

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);
}
};

static inline int Find (int pos, int DIM)
{
    return (pos + DIM - 1) / DIM;
}

static inline int GetKey (PII A)
{
    return ((1LL * A.first * Base) % (1LL * Mod) + A.second) % Mod;
}

static inline void Read ()
{
    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 = InParser :: Int(), Y = InParser :: Int();
        int Bucket_X = Find(X, W), Bucket_Y = Find(Y, H);

        Hash[GetKey({Bucket_X, Bucket_Y})].push_back({X, Y});
    }

    return;
}

auto Ok = [] (PII A, PII X)
{
    int X1 = A.first, Y1 = A.second;
    int X2 = X1 + W, Y2 = Y1 + H;

    if(X.first >= X1 && X.first <= X2 && X.second >= Y1 && X.second <= Y2)
        return 1;

    return 0;
};

static inline bool Check (int X, int Y)
{
    int Bucket_X = Find(X, W), Bucket_Y = Find(Y, H);

    for(int i = 0; i < 9; ++i)
    {
        int b_X = Bucket_X + dx[i], b_Y = Bucket_Y + dy[i];

        if(b_X < 1 || b_Y < 1)
            continue;

        int Key = GetKey({b_X, b_Y});

        for(auto it : Hash[Key])
            if(Ok(it, {X, Y}))
                return 1;
    }
}

static inline void Solve ()
{
    int ans = 0;

    for(int i = 1; i <= M; ++i)
    {
        int X = InParser :: Int(), Y = InParser :: Int();

        if(Check(X, Y))
            ++ans;
    }

    printf("%d\n", ans);

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}