Cod sursa(job #963718)

Utilizator darrenRares Buhai darren Data 18 iunie 2013 17:23:34
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("ograzi.in");
ofstream fout("ograzi.out");

char parse[1 << 18], *now;
inline void verify()
{
    if (*now == 0)
    {
        fin.get(parse, 1 << 18, '\0');
        now = parse;
    }
}
int get()
{
    while (*now < '0' || *now > '9')
    {
        ++now;
        verify();
    }

    int num = 0;
    while (*now >= '0' && *now <= '9')
    {
        num = num * 10 + (*now - '0');
        ++now;
        verify();
    }

    return num;
}

const int D1[] = {0, 1, 0, 1},
          D2[] = {0, 0, 1, 1};

const int MOD = 10009;

vector<pair<pair<int, int>, int> > HASH[MOD];
void Insert(int i1, int i2, int pos)
{
    int val = (1000007LL * i1 + i2) % MOD;
    HASH[val].push_back(make_pair(make_pair(i1, i2), pos));
}
int Find(int i1, int i2)
{
    int val = (1000007LL * i1 + i2) % MOD;
    for (vector<pair<pair<int, int>, int> >::iterator it = HASH[val].begin(); it != HASH[val].end(); ++it)
        if (it->first == make_pair(i1, i2))
            return it->second;
    return 0;
}

int N, M, W, H;
pair<int, int> A[50002];
int result;

int main()
{
    now = parse;
    verify();

    N = get();
    M = get();
    W = get();
    H = get();
    for (int i = 1; i <= N; ++i)
    {
        A[i].first = get();
        A[i].second = get();

        Insert(A[i].first / W + 1, A[i].second / H + 1, i);
    }

    for (int i = 1, nx, ny; i <= M; ++i)
    {
        nx = get();
        ny = get();

        int ax = nx / W, ay = ny / H;

        bool found = false;
        for (int k = 0; k < 4 && !found; ++k)
        {
            int act = Find(ax + D1[k], ay + D2[k]);
            if (act != 0 && nx >= A[act].first && ny >= A[act].second && nx <= A[act].first + W && ny <= A[act].second + H)
                found = true;
        }

        result += found;
    }

    fout << result << '\n';
}