Cod sursa(job #1584725)

Utilizator hrazvanHarsan Razvan hrazvan Data 30 ianuarie 2016 13:57:04
Problema Ograzi Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <stdio.h>
#define MAXN 50000
#define MAXM 100000
#define BUFF (1 << 17)
#define MOD 666019
#define P 1007
typedef struct{
  int x, y;
}punct;
punct v[MAXN], 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 (x * P + y) % 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;
  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);
  }
  for(i = 0; i < m; i++){
    v[i].x = readnr();
    v[i].y = readnr();
  }
  int rez = 0, ad, poz;
  for(i = 0; i < m; i++){
    x = v[i].x / w;  y = v[i].y / h;
    x = hash_val(x, y);
    ad = 0;
    poz = ult[x];
    while(poz != -1 && !ad){
      if(interior(hash[poz].x, hash[poz].y, v[i].x, v[i].y))
        ad = 1;
      poz = next[poz];
    }
    rez += ad;
  }
  FILE *out = fopen("ograzi.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}