Cod sursa(job #1364657)

Utilizator gapdanPopescu George gapdan Data 27 februarie 2015 19:26:39
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <vector>

#define MOD 131071
#define NMAX 50010
#define V 103

using namespace std;

struct punct
{
    int x;
    int y;
};

int n, m, w, h, i, j, k, poz, sol, p1, p2;
int  l[MOD+40];
vector<int>H[MOD+30];
punct v[NMAX], p, q;

void bagahash(int x, int y)
{
    int p1, p2, sol;
    p1=x/w;
    p2=y/h;
    if(x%w==0) p1--;
    if(y%h==0) p2--;
    sol=(p1*V+p2)%MOD;
    H[sol].push_back(i);
}

int main()
{
    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &w, &h);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d", &v[i].x, &v[i].y);
        v[i].x++;
        v[i].y++;
        bagahash(v[i].x, v[i].y);
        bagahash(v[i].x+w, v[i].y);
        bagahash(v[i].x, v[i].y+h);
        bagahash(v[i].x+w, v[i].y+h);
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &p.x, &p.y);

        p.x++;
        p.y++;
        p1=(p.x)/w;
        p2=(p.y)/h;

        if((p.x)%w==0) p1--;
        if((p.y)%h==0) p2--;

        poz=(p1*V+p2)%MOD;

       for(int j = 0; j < H[poz].size(); ++j)
        {
            q=v[H[poz][j]];
            if(q.x<=p.x && p.x<=q.x+w && q.y<=p.y && p.y<=q.y+h)
            {
                sol++;
                break;
            }
        }
    }
    printf("%d\n", sol);
    return 0;
}