Cod sursa(job #94619)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 24 octombrie 2007 09:49:51
Problema Ograzi Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

//#include <vector>
//using namespace std;

#define NMAX 100010

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

int N, M, Hash[(1<<22)+10], W, H;
long long S=((1<<22)-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 hash, 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;
                c = D[i].x2/W;
                hash = 65599;
                hash = c+(hash<<6)+(hash<<16)-hash;
                c = D[i].y2/H;
                hash = (c+(hash<<6)+(hash<<16)-hash)&S;

				if (Hash[hash])
				{
					return 69;
				}

				Hash[ hash ] = i;
        }

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

                c = x/W;
                hash = 65599;
                hash = c+(hash<<6)+(hash<<16)-hash;
                c = y/H;
                hash = (c+(hash<<6)+(hash<<16)-hash)&S;
                d = Hash[hash];
                nsol += include(x,y,d);

                c = 1+(x/W);
                hash = 65599;
                hash = c+(hash<<6)+(hash<<16)-hash;
                c = y/H;
                hash = (c+(hash<<6)+(hash<<16)-hash)&S;
                d = Hash[hash];
                nsol += include(x,y,d);

                c = 1+(x/W);
                hash = 65599;
                hash = c+(hash<<6)+(hash<<16)-hash;
                c = 1+(y/H);
                hash = (c+(hash<<6)+(hash<<16)-hash)&S;
                d = Hash[hash];
                nsol += include(x,y,d);

                c = x/W;
                hash = 65599;
                hash = c+(hash<<6)+(hash<<16)-hash;
                c = 1+(y/H);
                hash = (c+(hash<<6)+(hash<<16)-hash)&S;
                d = Hash[hash];
                nsol += include(x,y,d);
        }

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

        return 0;
        
}