Cod sursa(job #1506026)

Utilizator akaprosAna Kapros akapros Data 19 octombrie 2015 22:35:36
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define mod 666013
#define maxN 50002
#define maxM 100002
#define inf 1000002
#define ll long long
using namespace std;
struct point
{
    int x;
    int y;
    ll val;
};
ll val;
int i, j, n, m, w, h, x, y, sol;
vector < point > V[mod];
int ok(point a, point b)
{
    return a.x <= b.x && b.x <= a.x + w && a.y <= b.y && b.y <= a.y + h;
}
int In_hash(ll val, point sheep)
{
    ll x = val % mod, a, b;
    int i, l = V[x].size();
    for (i = 0; i < l; ++ i)
        if (V[x][i].val == val && ok(V[x][i], sheep))
            return 1;
    return 0;
}
void read()
{
    point orch;
    freopen("ograzi.in", "r", stdin);
    scanf("%d %d %d %d", &n, &m, &w, &h);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &x, &y);
        val = (long long)((x / w) * inf * 1LL + (y / h) * 1LL);
        orch.x = x; orch.y = y;
        orch.val = val;
        V[val % mod].push_back(orch);
    }
}
void solve()
{
    int z, t;
    point sheep;
    while (m --)
    {
        scanf("%d %d", &x, &y);
        sheep.x = x;
        sheep.y = y;
        for (z = -1; z < 1; ++ z)
            for (t = -1; t < 1; ++ t)
            {
                ll val = (long long)(((x / w) + z) * inf * 1LL + (y / h) * 1LL + t);
                if (val >= 0 && In_hash(val, sheep))
                {
                    ++ sol;
                    z = 1;
                    t = 1;
                }
            }
    }
}
void write()
{
    freopen("ograzi.out", "w", stdout);
    printf("%d", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}