Cod sursa(job #2201418)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 4 mai 2018 18:15:38
Problema Ograzi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 666013;

vector<pair<int, int> >mp[MOD + 5];
pair<int, int>x[50005];
int w, h;
int j;

class InParser {
private:
  FILE *fin;
  char *buff;
  int sp;

  char read_ch() {
    ++sp;
    if (sp == 131072) {
      sp = 0;
      fread(buff, 1, 131072, fin);
    }
    return buff[sp];
  }

public:
  InParser(const char* nume) {
    fin = fopen(nume, "r");
    buff = new char[131072]();
    sp = 131071;
  }

  InParser& operator >> (int &n) {
    char c;
    while (!isdigit(c = read_ch()) && c != '-');
    int sgn = 1;
    if (c == '-') {
      n = 0;
      sgn = -1;
    } else {
      n = c - '0';
    }
    while (isdigit(c = read_ch())) {
      n = 10 * n + c - '0';
    }
    n *= sgn;
    return *this;
  }
};

int in(int xj, int yj, int xs, int ys, pair<int, int>pct) {
  if (xj <= pct.first && pct.first <= xs && yj <= pct.second && pct.second <= ys)
    return 1;
  return 0;
}

int check(int x2, int y2, int nr) {
  int aux = (1LL * x2 * nr + y2) % MOD;
  int ans = 0;
  int x1 = x[j].first;
  int y1 = x[j].second;
  for (auto it:mp[aux])
    ans += in(x1, y1, x1 + w, y1 + h, it);
  return ans;
}

int main() {
  InParser fin("ograzi.in");
  freopen("ograzi.out", "w", stdout);

  int n, m;
  fin >> n >> m >> w >> h;
  for (int i = 1; i <= n; ++i)
    fin >> x[i].first >> x[i].second;
  int nr = 1.e6 / h + 1;
  for (int i = 1; i <= m; ++i) {
    pair<int, int>aux;
    fin >> aux.first >> aux.second;
    int px = aux.first / w;
    int py = aux.second / h;
    mp[(1LL * px * nr + py) % MOD].push_back(aux);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    j = i;
    int x1 = x[i].first / w;
    int y1 = x[i].second / h;
    ans += check(x1, y1, nr) + check(x1, y1 + 1, nr) + check(x1 + 1, y1, nr) + check(x1 + 1, y1 + 1, nr);
  }
  printf("%d\n", ans);
  return 0;
}