Cod sursa(job #1733822)

Utilizator tudi98Cozma Tudor tudi98 Data 25 iulie 2016 20:45:00
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <utility>
#include <vector>
using namespace std;
#define Mod 666013

int N,M,W,H;

int h(int x,int y)
{
    return (x * 31 + y) % Mod;
}

vector< pair<int,int> > Hash[Mod+4];

bool get(int X,int Y,int x,int y)
{
    int i = h(X,Y);
    for (auto j: Hash[i])
        if (x >= j.first && y >= j.second && x <= j.first + W && y <= j.second + H) return 1;
    return 0;
}

int main()
{
    //InputReader fin = InputReader("ograzi.in");
    ifstream fin("ograzi.in");
    ofstream fout("ograzi.out");

    fin >> N >> M >> W >> H;
    for (int i = 1; i <= N; i++)
    {
        int x,y,X,Y;
        fin >> x >> y;
        X = x/W*W; Y = y/H*H;
        Hash[h(X,Y)].push_back(make_pair(x,y));
    }

    int Sol = 0;
    for (int i = 1; i <= M; i++)
    {
        int x,y,X,Y;
        fin >> x >> y;
        X = x / W * W;
        Y = y / H * H;
        if (get(X,Y,x,y)) Sol++;
        else if (get(X-W,Y,x,y)) Sol++;
        else if (get(X-W,Y-H,x,y)) Sol++;
        else if (get(X,Y-H,x,y)) Sol++;
    }

    fout << Sol << "\n";
}