Cod sursa(job #25334)

Utilizator 004444Lapusan Tudor 004444 Data 4 martie 2007 12:02:50
Problema Ograzi Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 3.1 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
#define LGN  18

struct point
{
	int x, y;
}P[MAXN], dr[50002], aux;

typedef struct point point;

int N, M, X[MAXN], T[150][MAXN], x1, y1, x2, y2, w, h, sol;
/*
int cmp(const void *i, const void *j)
{
    return ((point *)i)->x - ((point *)j)->x;
}
*/

void build(int lv, int l, int r)
{
    int m = (l + r) >> 1, i, j, k;

    if (l == r)
    {
        T[lv][l] = P[l].y; 
        return; 
    }

    build(lv+1, l, m);
    build(lv + 1, m+1, r);

    for (i=l, j=m + 1, k=l; i<=m || j <= r; )
        if (j > r || (i <= m && T[lv+1][i] < T[lv+1][j]))
          	T[lv][k++] = T[lv + 1][i++];
        else
           	T[lv][k++] = T[lv + 1][j++]; 
}

int search(int A[], int l, int r, int v)
{
    int pp, step;

	if (v < A[l])
		return l - 1;

    for (step=1; step < (r-l + 1); step <<= 1);

    for (pp = l; step; step >>= 1)
    	if (pp + step <= r && A[pp + step] <= v)
       		pp += step;

    return pp;
}

int query(int lv, int l, int r)
{
    int m, t = 0;

    if (x1 <= l && r <= x2)
    {
//	   if (y2 < T[lv][l] || y1 > T[lv][r])
  //       return 0;
       if (y2 < T[lv][l] || y1 > T[lv][r])
          return 0;

       if (y1 < T[lv][l] && T[lv][r] < y2)
          return (r - l + 1);

	   t=search(T[lv], l, r, y2) - search(T[lv], l, r, y1 - 1);
   	}
  	else
 	{
	 	m = (l + r) >> 1;

		if (x1 <= m)
			t += query(lv + 1, l, m);
		if (x2 > m)
			t += query(lv + 1, m + 1, r);
  	}
  	return t;
}

void qsort ( int prim, int ultim )
{
	int i, j, mij;


	i = prim;
	j = ultim;
	mij = P[(i + j) / 2].x;

	do
	{
		while ( P[i].x < mij )
			i++;
		while ( P[j].x > mij )
			j--;

		if ( i <= j )
		{
			aux = P[i];
			P[i] = P[j];
			P[j] = aux;
			i++;
			j--;
		}
	}
	while ( i <= j );

	if ( i < ultim )
		qsort ( i, ultim );
	if ( j > prim )
		qsort ( prim, j );
}

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

//    printf ("^fds" );

	scanf ("%d %d", &N, &M);
	scanf ( "%d %d", &w, &h );
	for (i = 0; i < N; i++)
	  scanf ("%d %d", &dr[i].x, &dr[i].y);

	//qsort(P, N, sizeof(point), cmp);

//	for (i = 0; i < N; i++)
//		X[i] = P[i].x;

	for ( i = 0; i < M; i++ )
		scanf ( "%d %d", &P[i].x, &P[i].y );
	qsort ( 1, M - 1 );
	for (i = 0; i < M; i++)
		X[i] = P[i].x;

//	for ( i = 1; i <= M; i++ )
//		printf ( "%d %d\n", dr[i].x, dr[i].y );

	build(0, 0, M - 1);

//	for ( i = 1; i <= M; i++ )
//    	printf ( "%d ", X[i] );
	for (i = 0; i < N; i++ )
	{
		//x2 = dr[i].x;
		//y2 = dr[i].y;
		//y1 = y2 + h;
		//x1 = x2 + w;

		x1 = dr[i].x;
		y1 = dr[i].y + h;
		x2 = x1 + w;
		y2 = y1 - h;
        o = y1;
        y1 = y2;
        y2 = o;

//     	if (x2 < X[1] || x1 > X[M])
//       		fprintf(fout, "0\n");
//     	else
		{
			x1 = search(X, 0, M - 1, x1 - 1) + 1;
   			x2 = search(X, 0, M - 1, x2);
// 			fprintf(fout, "%d\n", query(1, 1, M));
            sol += query ( 0, 0, M - 1 );
        }
    }
	printf ( "%d\n", sol );

    return 0;
}