Cod sursa(job #961091)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 16:59:41
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#define mod 666013
#define B_size 1000000
using namespace std;
 
int N, M, W, H;
pair <int, int> O[50011];
vector <int> map[mod];
const int val1[] = {0, -1, 0, -1};
const int val2[] = {0, 0, -1, -1};
char buffer[B_size];
int B;
 
inline int Hash_val (const int x, const int y)
{
    return (1LL * x * 1000001 + y) % mod;
}
 
inline bool Inside (const int x, const int y, const int i)
{
    const int x1 = O[i].first;
    const int y1 = O[i].second;
    if (x >= x1 && x <= x1 + W && y >= y1 && y <= y1 + H) return 1;
    return 0;
}
 
inline int get_num ()
{
    while (buffer[B] < '0' || buffer[B] > '9')
        if (++B == B_size) fread (buffer, 1, B_size, stdin), B = 0;
    int x = 0;
    while (buffer[B] >= '0' && buffer[B] <= '9')
    {
        x = x * 10 + buffer[B] - '0';
        if (++B == B_size) fread (buffer, 1, B_size, stdin), B = 0;
    }
    return x;
}
 
int main ()
{
    freopen ("ograzi.in", "r", stdin);
    freopen ("ograzi.out", "w", stdout);
    fread (buffer, 1, 1000000, stdin);
    N = get_num (), M = get_num (), W = get_num (), H = get_num ();
    for (int i = 0, x, y; i < N; i++)
    {
        x = get_num (), y = get_num ();
        O[i].first = x;
        O[i].second = y;
        x /= W, y /= H;
        map[Hash_val (x, y)].push_back (i);
    }
    int cnt = 0;
    for (; M; M--)
    {
        const int x = get_num (), y = get_num ();
        int good = 0;
        for (int j = 0; j <= 3; j++)
            if (!good)
            {
                const int alfa = x / W + val1[j], beta = y / H + val2[j];
                if (alfa >= 0 && beta >= 0)
                {
                    const int dog = Hash_val (alfa, beta);
                    for (int i = 0; i < (int) map[dog].size (); i++)
                        if (Inside (x, y, map[dog][i])) good = 1;
                }
            }
        cnt += good;
    }
    printf ("%d", cnt);
    return 0;
}