Cod sursa(job #21)

Utilizator filipbFilip Cristian Buruiana filipb Data 2 decembrie 2006 15:59:22
Problema Zoo Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.75 kb
/* Time Complexity: O(N log^2 N)

     2D Ortogonal Range Search ( without Willad-Lueker improvement )
*/

#include <stdio.h>
#include <stdlib.h>
#define filein "zoo.in"
#define fileout "zoo.out"
#define logN 16
#define NMax 16000 
typedef struct {
		 int x;
		 int y;
	       } coord;
typedef coord vector[NMax + 1];
typedef int stiva[NMax + 1];
typedef stiva ARBORE[logN + 1];

int n;
vector v;

stiva X;
ARBORE A;

int x1, y1, x2, y2;

int cmp(const void *a, const void *b)
{ coord *A = (coord *)a, *B = (coord *)b;
  return (A->x - B->x);
}

void buildTree(int lv, int st, int dr)
{ int i, l, r, m;

  if (st == dr)
   A[lv][st] = v[st].y;
  else
  {
     m = (st + dr) / 2;
     buildTree(lv + 1, st, m); buildTree(lv + 1, m + 1, dr);
     for (l = st, r = m+1, i = st; i <= dr; i++)
      if ((l <= m && A[lv+1][l] <= A[lv+1][r]) || (r > dr))
       A[lv][i] = A[lv+1][l++];
      else
       A[lv][i] = A[lv+1][r++];
  }
}

int BSearch(stiva X, int start, int finish, int Key, int action)
{ int st, dr, mid, index = 0;

  st = start, dr = finish;
  while (st <= dr)
  {
     mid = (st + dr) / 2;
     if (!action) // primul index >= Key
     {
	if (X[mid] < Key)      st = mid + 1;
	else 		       index = mid, dr = mid - 1;
     }
     else	  // ultimul index <= Key
     {
	if (X[mid] > Key)      dr = mid - 1;
	else		       index = mid, st = mid + 1;
     }
  }

  return index;
}

int query(int lv, int st, int dr)
{ int i, mid, i1, i2, x, t;


   if (x1 <= st && dr <= x2)
   {
     if (y1 > A[lv][dr] || y2 < A[lv][st]) return 0;

     i1 = BSearch(A[lv], st, dr, y1, 0);
     i2 = BSearch(A[lv], st, dr, y2, 1);

     return (i2 - i1 + 1);
   }
   else
   {
      t = 0; mid = (st + dr) / 2;
      if (x1 <= mid) t += query(lv + 1, st, mid);
      if (x2 > mid)  t += query(lv + 1, mid + 1, dr);
      return t;
   }
}

void solve()
{ FILE *fin = fopen(filein, "r"), *fout = fopen(fileout, "w");
  int i, m, a, b, c, d;
  int nr;

	fscanf(fin, "%d", &n);
	for (i = 0; i < n; i++)
	 fscanf(fin, "%d %d", &v[i].x, &v[i].y);

	qsort(v, n, sizeof(coord), cmp);

	for (i = 0; i < n; i++) X[i] = v[i].x;
	for (i = n; i >= 1; i--) X[i] = X[i-1];
	X[0] = 0;

	for (i = n; i >= 1; i--) v[i] = v[i-1];
	v[i].x = v[i].y = 0;

	buildTree(1, 1, n);

	fscanf(fin, "%d", &m);
	for (i = 1; i <= m; i++)
	{
	  fscanf(fin, "%d %d %d %d", &a, &b, &c, &d);

	  if (a > X[n] || c < X[1] || b > A[1][n] || d < A[1][1])
	   fprintf(fout, "0\n");
	  else
	  {

	    x1 = BSearch(X, 1, n, a, 0);
	    x2 = BSearch(X, 1, n, c, 1);
	    y1 = b, y2 = d;

	    nr = query(1, 1, n);

	    fprintf(fout, "%d\n", nr);
	  }

	}


  fclose(fin); fclose(fout);
}

int main()
{
	solve();
	return 0;
}