Cod sursa(job #915931)

Utilizator cbanu96Banu Cristian cbanu96 Data 15 martie 2013 16:14:23
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <vector>

#define MOD 123331
#define NMAX 50002
#define FILEIN "ograzi.in"
#define FILEOUT "ograzi.out"

using namespace std;


int w,h,N,M,sol=0;
int x,y;
int V[NMAX][2];

vector<int> H[MOD];

inline int hashf(int a, int b)
{
    return (a * 100 + b)%MOD;
}

inline int search(int a, int b,int x, int y)
{
    int k = (a * 100 + b)%MOD;
    for ( int i = 0; i < H[k].size(); i++)
    {
        int p = H[k][i];
        if(V[p][0] <= x && x <= V[p][0] + w && V[p][1] <= y && V[p][1] + h)
        {
            sol++;
            return 1;
        }
    }
    return 0;
}

int main()
{
    int i, j, x1, y1;
    ifstream f(FILEIN);
    ofstream g(FILEOUT);
    f >> N >> M >> w >> h;
    for ( i = 1; i <= N; i++)
    {
        f >> x >> y;
        V[i][0] = x; V[i][1] = y;
        x1 = (x+w-1)/h;
        y1 = (y+h-1)/w;
        H[hashf(x1,y1)].push_back(i);
    }
    for ( i = 1; i <= M; i++)
    {
        f >> x >> y;
        x1 = (x+w-1)/w;
        y1 = (y+h-1)/h;
        search(x1,y1,x,y);
        search(x1,y1-1,x,y);
        search(x1-1,y1,x,y);
        search(x1-1,y1-1,x,y);
    }
    f.close();
    g << sol << '\n';
    g.close();
    return 0;
}