Cod sursa(job #319095)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 30 mai 2009 15:29:19
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <stdio.h>

#define mod 166013
#define maxn 50010
using namespace std;

struct punct
{
    long x;
    long y;
};
long n, m, w, h, i, j, k, poz, sol, p1, p2;
long hs[mod+10][20], l[mod+10];
punct c[maxn], p, q;

void hash(long x, long y)
{
    long p1, p2, sol;
    p1=x/w;
    p2=y/h;
    if(x%w==0) p1--;
    if(y%h==0) p2--;
 //   printf("%d %d\n", p1, p2);
    sol=(p1*1013+p2*13)%mod;
    hs[sol][++l[sol]]=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", &c[i].x, &c[i].y);
        hash(c[i].x, c[i].y);
        hash(c[i].x+w, c[i].y);
        hash(c[i].x, c[i].y+h);
        hash(c[i].x+w, c[i].y+h);
     //   printf("\n");
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &p.x, &p.y);
        p1=(p.x)/w;
        p2=(p.y)/h;
      //  printf("%d %d\n", p1, p2);
        if((p.x)%w==0) p1--;
        if((p.y)%h==0) p2--;
        poz=(p1*1013+p2*13)%mod;
        
        for(j=1; j<=l[poz]; j++)
        {
            q=c[hs[poz][j]];
     //       printf("%d ", hs[poz][j]);
            if(q.x<=p.x && p.x<=q.x+w && q.y<=p.y && p.y<=q.y+h)
            {
                sol++;
                break;
            }
        }
    //    printf("\n");
    }
    printf("%d\n", sol);
    return 0;
}