Cod sursa(job #942331)

Utilizator SteveStefan Eniceicu Steve Data 21 aprilie 2013 21:14:19
Problema Ograzi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#define mod 1000003
using namespace std;

int N, M, W, H;
pair <int, int> ograzi[mod];
vector <int> map[mod];
int val1[] = {0, -1, 0, -1};
int val2[] = {0, 0, -1, -1};
char pars[17];
char *buffer;

int Inside (int x, int y, int i)
{
    int x1 = ograzi[i].first;
    int y1 = ograzi[i].second;
    if (x >= x1 && x <= x1 + W && y >= y1 && y <= y1 + H) return 1;
    return 0;
}

void get_num (int &x)
{
    for (; *buffer < '0' || *buffer > '9'; buffer++);
    x = 0;
    for (; *buffer >= '0' && *buffer <= '9'; buffer++)
        x = x * 10 + *buffer - '0';
}

int main ()
{
    freopen ("ograzi.in", "r", stdin);
    freopen ("ograzi.out", "w", stdout);
    fseek (stdin, 0, SEEK_END);
    int A = ftell(stdin);
    buffer = (char*) malloc (A);
    rewind (stdin);
    fread (buffer, 1, A, stdin);
    fclose (stdin);
    get_num (N), get_num (M), get_num (W), get_num (H);
    for (int i = 0, x, y; i < N; i++)
    {
        get_num (x), get_num (y);
        ograzi[i].first = x;
        ograzi[i].second = y;
        x /= W, y /= H;
        map[(1LL * x * 50001 + y) % mod].push_back (i);
    }
    int cnt = 0;
    for (int i = 0, x, y; i < M; i++)
    {
        get_num (x), get_num (y);
        int good = 0;
        for (int j = 0; j <= 3; j++)
            if (!good)
            {
                int alfa = x / W + val1[j], beta = y / H + val2[j];
                if (alfa >= 0 && beta >= 0)
                    for (int i = 0; i < (int) map[(1LL * alfa * 50001 + beta) % mod].size (); i++)
                        if (Inside (x, y, map[(1LL * alfa * 50001 + beta) % mod][i])) good = 1;
            }
        cnt += good;
    }
    printf ("%d", cnt);
    return 0;
}