Cod sursa(job #1680772)

Utilizator stoianmihailStoian Mihail stoianmihail Data 9 aprilie 2016 09:09:23
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <stdio.h>
#include <ctype.h>

#define Nadejde 16000
#define Dragoste 4096

struct pair {
  int x, y;
};

int N, M;
int x1, y1, x2, y2;
pair point[Nadejde];

char buff[Dragoste];
int ptr = Dragoste;

char getChar(FILE *f) {
  if (ptr == Dragoste) {
    fread(buff, 1, Dragoste, f);
    ptr = 0;
  }
  return buff[ptr++];
}

int freef(FILE *f) {
  int result = 0;
  char c = '#', sign;

  do {
    sign = c;
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  if (sign == '-') {
    return -result;
  } else {
    return result;
  }
}

int inside(int pos) {
  return y1 <= point[pos].y && point[pos].y <= y2;
}

void sort(int begin, int end) {
  int b = begin, e = end;
  pair tmp, pivot = point[(b + e) >> 1];

  while (b <= e) {
    while (point[b].x < pivot.x) {
      b++;
    }
    while (pivot.x < point[e].x) {
      e--;
    }
    if (b <= e) {
      tmp = point[b];
      point[b++] = point[e];
      point[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

int bSearch(int lo, int hi, int x) {
  while (hi - lo > 1) {
    int mid = (lo + hi) >> 1;
    if (x > point[mid].x) {
      lo = mid;
    } else {
      hi = mid;
    }
  }
  //fprintf(stderr, "%d\n", hi);
  return hi;
}

void v(int val) {
  fprintf(stderr, "%d -> %d\n", val, bSearch(-1, N, val));
}

int main(void) {
  int i, j, count;
  FILE *f = fopen("zoo.in", "r");
  freopen("zoo.out", "w", stdout);

  N = freef(f);
  //fprintf(stderr, "%d\n", N);
  for (i = 0; i < N; i++) {
    point[i].x = freef(f);
    point[i].y = freef(f);
   // fprintf(stderr, "%d %d\n", point[i].x, point[i].y);
    //fscanf(f, "%d %d", &point[i].x, &point[i].y);
  }

  sort(0, N - 1);
/*
  for (i = 0; i < N; i++) {
    fprintf(stderr, "%d, ", point[i].x);
  }
  fprintf(stderr, "\n");

  v(1);
  v(0);
  v(3);
*/
  M = freef(f);
  //fprintf(stderr, "%d\n", M);
  for (i = 0; i < M; i++) {
    //fscanf(f, "%d %d %d %d", &x1, &y1, &x2, &y2);
    x1 = freef(f);
    y1 = freef(f);
    x2 = freef(f);
    y2 = freef(f);

 //   fprintf(stderr, "%d %d %d %d\n", x1, y1, x2, y2);
    count = 0;
    for (j = bSearch(-1, N, x1); (j < N) && (point[j].x <= x2); j++) {
      if (inside(j)) {
        count++;
      }
    }
    fprintf(stdout, "%d\n", count);
  }
  fclose(f);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}