Cod sursa(job #1584664)

Utilizator hrazvanHarsan Razvan hrazvan Data 30 ianuarie 2016 12:51:42
Problema Ograzi Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <stdio.h>
#define MAXN 50000
#define MAXM 100000
#define BUFF (1 << 17)
#define MOD 666019
#define P1 666013
#define P2 1114111
typedef struct{
  int x, y;
}punct;
punct v[MAXN], hash[MAXM];
int ult[MOD], next[MAXM], dh;
FILE *in;
int pin;
char s[BUFF];
int w, h;


inline char cif(char x){
  if(x >= '0' && x <= '9')
    return 1;
  return 0;
}

inline char readch(){
  if(pin == BUFF){
    fread(s, 1, BUFF, in);
    pin = 0;
  }
  pin++;
  return s[pin - 1];
}

inline int readnr(){
  int rez = 0;
  char ch;
  ch = readch();
  while(!cif(ch))
    ch = readch();
  while(cif(ch)){
    rez *= 10;
    rez += ch - '0';
    ch = readch();
  }
  return rez;
}

inline int max2(int a, int b){
  return a > b ? a : b;
}

inline int hash_val(int x, int y){
  return (1LL * x * P1 + 1LL * y * P2 + 1LL * MOD * MOD) % MOD;
}

inline char interior(int a, int b, int x, int y){
  if(x - a < w && x - a >= 0 && y - b < h && y - b >= 0)
    return 1;
  return 0;
}

inline void add(int a, int b){
  int x, y, k;
  x = a / w;  y = b / h;
  if(x * w == a)
    x--;
  if(y * h == b)
    y--;
  x++;  y++;
  k = hash_val(x, y);
  hash[dh].x = a;  hash[dh].y = b;
  next[dh] = ult[k];
  ult[k] = dh;
  dh++;
}

inline int caut(int x, int y, int a, int b){
  int k, poz;
  k = hash_val(x, y);
  poz = ult[k];
  while(poz != -1){
    if(interior(hash[poz].x, hash[poz].y, a, b))
      return 1;
    poz = next[poz];
  }
  return 0;
}

int main(){
  in = fopen("ograzi.in", "r");
  int n, m, i, x, y;
  n = readnr();  m = readnr();  w = readnr();  h = readnr();
  memset(ult, -1, sizeof ult);
  for(i = 0; i < n; i++){
    x = readnr();  y = readnr();
    add(x, y);
  }
  for(i = 0; i < m; i++){
    v[i].x = readnr();
    v[i].y = readnr();
  }
  int rez = 0, add;
  for(i = 0; i < m; i++){
    x = v[i].x / w;  y = v[i].y / h;
    if(x * w == v[i].x)
      x--;
    if(y * h == v[i].y)
      y--;
    add = 0;
    add = max2(add, caut(x, y, v[i].x, v[i].y));
    add = max2(add, caut(x, y + 1, v[i].x, v[i].y));
    add = max2(add, caut(x + 1, y, v[i].x, v[i].y));
    add = max2(add, caut(x + 1, y + 1, v[i].x, v[i].y));
    rez += add;
  }
  FILE *out = fopen("ograzi.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}