Cod sursa(job #915744)

Utilizator cbanu96Banu Cristian cbanu96 Data 15 martie 2013 12:07:45
Problema Ograzi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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 k = (a * 100 + 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++;
            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; x1 /= w;
        y1 = y+h-1; y1 /= h;
        H[hashf(x1,y1)].push_back(i);
    }
    for ( i = 1; i <= M; i++)
    {
        f >> x >> y;
        x1 = x+w-1; x1 /= w;
        y1 = y+h-1; y1 /= 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;
}