Cod sursa(job #25612)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 4 martie 2007 13:08:41
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define NMAX 50010
#define MMAX 100010
#define nd(a) (*(t_p *)(a))

typedef struct t_p
{
	int x, y;
};

void read();
void solve();
void build(int x, int y, int nrv);
int cmp(const void *a, const void *b);
int query(int x, int y, int nrv, int val);

int N, M, W, H, lix, lsx, step;
unsigned short int V[17][NMAX];
t_p A[NMAX], B[MMAX];
char S[32];

int main()
{
	freopen("ograzi.in", "r", stdin);
     freopen("ograzi.out", "w", stdout);

     read();
     qsort(A, N, sizeof(t_p), cmp);
     solve();
	return 0;
}

void read()
{
	int i, x, y, k, j;
     
	scanf("%d%d%d%d ", &N, &M, &W, &H);
     for(i = 0; i < N; i++)
     {
	    fgets(S, 32, stdin);
         k = strlen(S);
         S[k - 1] = '\0';
         k--;
         x = 0;
         for(j = 0; S[j] != ' '; j++)
	    x = x * 10 + S[j] - '0';
         y = 0;
         for(++j; S[j] != '\0'; j++)
	    y = y * 10 + S[j] - '0';
         A[i].x = x, A[i].y = y;
     }
     for(i = 0; i < M; i++)
     {
	    fgets(S, 32, stdin);
         k = strlen(S);
         S[k - 1] = '\0';
         k--;
         x = 0;
         for(j = 0; S[j] != ' '; j++)
	    x = x * 10 + S[j] - '0';
         y = 0;
         for(++j; S[j] != '\0'; j++)
	    y = y * 10 + S[j] - '0';
         B[i].x = x, B[i].y = y;
     }
}

int cmp(const void *a, const void *b)
{
	if(nd(a).x != nd(b).x)
     return nd(a).x - nd(b).x;
	return nd(a).y - nd(b).y;
}

void solve()
{
	int i, rez = 0, j, rezz = 0;

     /*for(i = 0; i < M; i++)
     for(j = 0; j < N; j++)
     	if(A[j].x <= B[i].x && A[j].x + W >= B[i].x && A[j].y <= B[i].y && A[j].y + H >= B[i].y)
          {
          rezz++;
          seen[i] = 1;
          break;
          }
	printf("%d\n", rezz);*/
     build(0, N - 1, 0);
     for(i = 0; i < M; i++)
     {
     	lix = B[i].x - W >= 0 ? B[i].x - W : 0;
          lsx = B[i].x;
          if(query(0, N - 1, 0, B[i].y - H >= 0 ? B[i].y - H : 0))
          rez++;
     }
     printf("%d\n", rez);
}

void build(int x, int y, int nrv)
{
	int key = (x + y) / 2, i, j, k;
     
     if(x == y) V[nrv][x] = x;
	if(x >= y) return;

     build(x, key, nrv + 1);
     build(key + 1, y, nrv + 1);
	k = x;
     for(i = x, j = key + 1; i <= key && j <= y;)
	if(A[V[nrv + 1][i]].y < A[V[nrv + 1][j]].y)
     V[nrv][k++] = V[nrv + 1][i], i++;
     else V[nrv][k++] = V[nrv + 1][j], j++;
     for(; i <= key; i++)
     V[nrv][k++] = V[nrv + 1][i];
     for(; j <= y; j++)
     V[nrv][k++] = V[nrv + 1][j];
}

int query(int x, int y, int nrv, int val)
{
	int key = (x + y) / 2;
     
	if(x > y) return 0;
     if(A[y].x < lix || A[x].x > lsx) return 0;
     
     if(lix <= A[x].x && A[y].x <= lsx)
     {
		int i;

          for(step = 1; step <= (y - x + 1); step <<= 1);
          for(i = x - 1; step; step >>= 1)
          if(i + step <= y && A[V[nrv][i + step]].y < val)
          i += step;
          if(i == y) return 0;
          if(A[V[nrv][i + 1]].y - val <= H) return 1;
          else return 0;
     }
     return query(x, key, nrv + 1, val) | query(key + 1, y, nrv + 1, val);
}