Cod sursa(job #2023325)

Utilizator cella.florescuCella Florescu cella.florescu Data 18 septembrie 2017 19:05:27
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

class instream {
  public:
    instream (const char *file) {
      f = fopen(file, "r");
      bp = BUFF_SIZE - 1;
      buff[bp] = 0;
    }
    ~instream () {
      fclose(f);
    }
    instream &operator >> (int &num) {
      while (isdigit(buff[bp]) == 0)
        next_char();
      num = 0;
      while (isdigit(buff[bp])) {
        num = num * 10 + buff[bp] - '0';
        next_char();
      }
      return *this;
    }
  private:
    FILE *f;
    static const int BUFF_SIZE = (1 << 17);
    int bp;
    char buff[BUFF_SIZE];
    void next_char() {
      if (++bp == BUFF_SIZE) {
        fread(buff, 1, BUFF_SIZE, f);
        bp = 0;
      }
    }
};

const int LOG = 17;
const int MOD = 30103;

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

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

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 1;
  return 0;
}

int main()
{
    int n, m, x, y, ans = 0;
    instream 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;
}