Cod sursa(job #915695)

Utilizator cbanu96Banu Cristian cbanu96 Data 15 martie 2013 11:02:38
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <vector>

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

using namespace std;


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

vector<int> H[MOD];

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

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

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;
        y1 = y/h;
        H[hashf(x1,y1)].push_back(i);
    }
    for ( i = 1; i <= M; i++)
    {
        f >> x >> y;
        x1 = x/w;
        y1 = y/h;
        search(x1,y1);
        search(x1,y1-1);
        search(x1-1,y1);
        search(x1-1,y1-1);
    }
    f.close();
    g << sol << '\n';
    g.close();
    return 0;
}