Cod sursa(job #2201414)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 4 mai 2018 18:03:49
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

unordered_map<long long, vector<pair<int, int> > >mp;
pair<int, int>x[50005];
int w, h;
int j;

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) {
  long long aux = 1LL * x2 * nr + y2;
  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() {
  freopen("ograzi.in", "r", stdin);
  freopen("ograzi.out", "w", stdout);

  int n, m;
  scanf("%d%d%d%d", &n, &m, &w, &h);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d", &x[i].first, &x[i].second);
  int nr = 1.e6 / h + 1;
  for (int i = 1; i <= m; ++i) {
    pair<int, int>aux;
    scanf("%d%d", &aux.first, &aux.second);
    int px = aux.first / w;
    int py = aux.second / h;
    mp[1LL * px * nr + py].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;
}