Cod sursa(job #68591)

Utilizator filipbFilip Cristian Buruiana filipb Data 28 iunie 2007 16:16:07
Problema Ograzi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define NMax    50005
#define MOD     417
#define pb      push_back

int N, M, W, H, ograzi[NMax][2], cnt;
vector<int> hash[MOD][MOD];

void add_to_hash(int xx, int yy, int drept)
{
    int lx = (int)(((double)xx - 0.5) / W) + 1,
        ly = (int)(((double)yy - 0.5) / H) + 1;

    hash[ lx % MOD ][ ly % MOD ].pb( drept );
}

int interior(int px, int py, int d)
{
    return ograzi[d][0] <= px && ograzi[d][1] <= py &&
    	px <= ograzi[d][0] + W && py <= ograzi[d][1] + H;
}

int find_hash(int x, int y, int px, int py)
{
	int i, sz;

    x %= MOD; y %= MOD;
	sz = hash[x][y].size();

    for (i = 0; i < sz; i++)
        if (interior(px, py, hash[x][y][i]))
            return 1;
            
	return 0;
}

int rectangle(int px, int py)
{
    int i = (int)(((double)px - 0.5) / W),
    	j = (int)(((double)py - 0.5) / H);

	if (find_hash(i, j, px, py))     return 1;
    if (find_hash(i, j+1, px, py))   return 1;
    if (find_hash(i+1, j, px, py))   return 1;
    if (find_hash(i+1, j+1, px, py)) return 1;
    return 0;    
}

int main(void)
{
	int i, x, y;
    
	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", &ograzi[i][0], &ograzi[i][1]);
        add_to_hash(ograzi[i][0], ograzi[i][1], i);
    }

    for (; M; M--)
    {
    	scanf("%d %d", &x, &y);
        cnt += rectangle(x, y);
    }
    
    printf("%d\n", cnt);

	return 0;
}