Cod sursa(job #1680770)

Utilizator stoianmihailStoian Mihail stoianmihail Data 9 aprilie 2016 08:54:04
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>

#define Nadejde 16000

struct pair {
  int x, y;

  bool operator < (pair other) {
    return this -> x < other.x;
  }
};

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

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] < pivot) {
      b++;
    }
    while (pivot < point[e]) {
      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);

  fscanf(f, "%d", &N);
  for (i = 0; i < N; i++) {
    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);
*/
  fscanf(f, "%d", &M);
  for (i = 0; i < M; i++) {
    fscanf(f, "%d %d %d %d", &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;
}