Cod sursa(job #907599)

Utilizator Theorytheo .c Theory Data 8 martie 2013 08:37:37
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<fstream>
#include<vector>
#include<cstring>

using namespace std;

#define x first
#define y second

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

const int Nmax = 50005;
const int Mmax = 100006;
const int Prime = (1<<20) - 1;
const int MaxP = 1000002;


int N; int M; int W; int H;int Count;

char *p, Parse[Nmax  * 14 + Mmax * 14];

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


inline int GetKey(int X,int Y){

    if(X < 0 || Y < 0) return -1;

    return ((1LL *  X * MaxP + Y ) & Prime);
}


inline int NextNumber(){

    int Number = 0;

    while(*p && !( *p >= '0' && *p <= '9')) ++p;

    while(*p >= '0' && *p <= '9') Number = Number * 10 + (*p - '0'), ++p;

    return Number;
}


void Read(){

    fin >> N >> M >> W >> H;

    fin.getline(Parse, Nmax * 14 + Mmax * 14, '\0'); p = Parse;

    for(int i = 1; i <= N; ++i){

        int X = NextNumber(); int Y = NextNumber();

        Hash[GetKey(X / W, Y / H)].push_back(make_pair(X, Y));
    }
}


void Solve(){

    for(int i = 1; i <= M; ++i){

        int X = NextNumber(); int Y = NextNumber();

        bool ok = true;

        for(int dx = 0; dx <= 1 && ok ; dx++)
            for(int dy = 0; dy <= 1 && ok ; dy++){

                int Key = GetKey(X / W - dx, Y / H - dy);

                for(int i = 0 ; i < Hash[Key].size(); ++i)

                    if(Hash[Key][i].x  <= X && Hash[Key][i].x + W >= X &&
                       Hash[Key][i].y  <= Y && Hash[Key][i].y + H >= Y)
                       ++Count, ok = false;
            }
    }
}

void Print(){

    fout << Count ;
}


int main(){

    Read();

    Solve();

    Print();

    return 0;
}