Cod sursa(job #68596)

Utilizator filipbFilip Cristian Buruiana filipb Data 28 iunie 2007 16:25:12
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <stdio.h>
#include <string.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, j, x, y, l, sp;
    char s[256];
    
	freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);

    scanf("%d %d %d %d\n", &N, &M, &W, &H);
    for (i = 1; i <= N; i++)
    {
    	fgets(s, sizeof(s), stdin);
        
        for (l = strlen(s), j = sp = 0; j < l; j++)
            if (s[j] >= '0' && s[j] <= '9')
                ograzi[i][sp] = ograzi[i][sp] * 10 + (s[j] - '0');
            else if (s[j] == ' ')
            {
            	sp++;
                if (sp > 1) break;
            }
            else break;

        add_to_hash(ograzi[i][0], ograzi[i][1], i);
    }

    for (; M; M--)
    {
    	fgets(s, sizeof(s), stdin);
        
        for (l = strlen(s), j = x = y = sp = 0; j < l; j++)
            if (s[j] >= '0' && s[j] <= '9')
            {
            	if (!sp)
                	x = x * 10 + (s[j] - '0');
                else if (sp == 1)
                	y = y * 10 + (s[j] - '0');
            }
            else if (s[j] == ' ')
            	sp++;
            else break;
    
        cnt += rectangle(x, y);
    }
    
    printf("%d\n", cnt);

	return 0;
}