Cod sursa(job #2023313)

Utilizator cella.florescuCella Florescu cella.florescu Data 18 septembrie 2017 18:46:09
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

const int LOG = 17;
const int MOD = (1 << LOG) - 1;

int mod(int x) {
  while (x >= MOD)
    x = (x >> LOG) + (x & ((1 << LOG) - 1));
  return x;
}

int hsh_key(int x, int y) {
  return mod(x * 1009 + y);
}


vector <pair <int, int>> hsh[MOD];
int dirx[] = {0, 0, -1, -1}, diry[] = {0, -1, 0, -1}, w, h;

int myfind(int x, int y, int d) {
  int wh = hsh_key(x / w + dirx[d], y / h + diry[d]);
  if (wh < 0)
    return 0;
  for (auto dr : hsh[wh])
    if (dr.first <= x && x <= dr.first + w && dr.second <= y && y <= dr.second + h)
      return true;
  return false;
}

int main()
{
    int n, m, x, y, ans = 0;
    ifstream fin("ograzi.in");
    fin >> n >> m >> w >> h;
    for (int i = 0; i < n; ++i) {
      fin >> x >> y;
      hsh[hsh_key(x / w, y / h)].push_back(make_pair(x, y));
    }
    for (int i = 0; i < m; ++i) {
      fin >> x >> y;
      for (int d = 0; d < 4; ++d)
        if (myfind(x, y, d)) {
          ++ans;
          d = 4;
        }
    }
    ofstream fout("ograzi.out");
    fout << ans;
    fout.close();
    return 0;
}