Cod sursa(job #94502)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 23 octombrie 2007 14:30:39
Problema Ograzi Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#define NMAX 100010
#define mix(a,b,c) \
{ \
  a -= b; a -= c; a ^= (c>>13); \
  b -= c; b -= a; b ^= (a<<8); \
  c -= a; c -= b; c ^= (b>>13); \
  a -= b; a -= c; a ^= (c>>12);  \
  b -= c; b -= a; b ^= (a<<16); \
  c -= a; c -= b; c ^= (b>>5); \
  a -= b; a -= c; a ^= (c>>3);  \
  b -= c; b -= a; b ^= (a<<10); \
  c -= a; c -= b; c ^= (b>>15); \
}


struct dreptunghi
{
        int x1, y1, x2, y2;
} D[NMAX];

int N, M, Hash[(1<<22)+10], W, H;
long long P=2066609, Q=3466681, S=4194287, PUT2 = ((1<<20)-1);

int include(int x, int y, int k)
{
        int x1 = D[k].x1, y1 = D[k].y1;
        int x2 = x1+W, y2 = y1+H;

        if ((x1<=x&&x<=x2)&&(y1<=y&&y<=y2)) return 1;
        else return 0;
}

int main()
{
        int i, x, y, nsol, d;
        long long rez, a, b, c;

        freopen("ograzi.in", "r", stdin);
        scanf("%d%d%d%d", &N, &M, &W, &H);

        for (i = 1; i <= N; i++)
        {
                scanf("%d%d", &D[i].x1, &D[i].y1);
                D[i].x2 = D[i].x1+W; D[i].y2 = D[i].y1+H;
                a = D[i].x2/W; b = D[i].y2/H;
                rez = (a*Q+P*b)&PUT2; c = rez;
                mix(a,b,c);
                a = a&PUT2; b = b&PUT2; c = c&PUT2;
                rez = ((a+b)*P+(c+a)*Q)%S;
                Hash[ rez ] = i;
        }

        for (i = nsol = 0; i < M; i++)
        {
                scanf("%d%d", &x, &y);

                a  = x/W; b = y/H;
                rez = (a*Q+P*b)&PUT2; c = rez;
                mix(a,b,c);
                a = a&PUT2; b = b&PUT2; c = c&PUT2;
                rez = ((a+b)*P+(c+a)*Q)%S;
                d = Hash[rez];
                nsol += include(x,y,d);

                a  = 1+(x/W); b = y/H;
                rez = (a*Q+P*b)&PUT2; c = rez;
                mix(a,b,c);
                a = a&PUT2; b = b&PUT2; c = c&PUT2;
                rez = ((a+b)*P+(c+a)*Q)%S;
                d = Hash[rez];
                nsol += include(x,y,d);

                a  = 1+(x/W); b = 1+(y/H);
                rez = (a*Q+P*b)&PUT2; c = rez;
                mix(a,b,c);
                a = a&PUT2; b = b&PUT2; c = c&PUT2;
                rez = ((a+b)*P+(c+a)*Q)%S;
                d = Hash[rez];
                nsol += include(x,y,d);

                a  = x/W; b = 1+(y/H);
                rez = (a*Q+P*b)&PUT2; c = rez;
                mix(a,b,c);
                a = a&PUT2; b = b&PUT2; c = c&PUT2;
                rez = ((a+b)*P+(c+a)*Q)%S;
                d = Hash[rez];
                nsol += include(x,y,d);
        }

        freopen("ograzi.out", "w", stdout);
        printf("%d\n", nsol);

        return 0;
        
}