Cod sursa(job #1584730)

Utilizator hrazvanHarsan Razvan hrazvan Data 30 ianuarie 2016 14:02:36
Problema Ograzi Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.94 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 hash[MAXM];
int ult[MOD], next[MAXM], dh;
FILE *in;
int pin = BUFF;
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 + 5 * 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 x, int y, int a, int b){
  int k = hash_val(x, y);
  hash[dh].x = a;  hash[dh].y = b;
  next[dh] = ult[k];
  ult[k] = dh;
  dh++;
}

int main(){
  in = fopen("ograzi.in", "r");
  int n, m, i, x, y, a, b, q, w;
  n = readnr();  m = readnr();  w = readnr();  h = readnr();
  memset(ult, -1, sizeof ult);
  for(i = 0; i < n; i++){
    a = readnr();  b = readnr();
    x = a / w + 1;  y = b / h + 1;
    add(x, y, a, b);
    add(x - 1, y, a, b);
    add(x, y - 1, a, b);
    add(x - 1, y - 1, a, b);
  }
  int rez = 0, ad, poz;
  for(i = 0; i < m; i++){
    q = readnr();  w = readnr();
    x = q / w;  y = w / h;
    x = hash_val(x, y);
    ad = 0;
    poz = ult[x];
    while(poz != -1 && !ad){
      if(interior(hash[poz].x, hash[poz].y, q, w))
        ad = 1;
      poz = next[poz];
    }
    rez += ad;
  }
  FILE *out = fopen("ograzi.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}