Cod sursa(job #877379)

Utilizator veleanduAlex Velea veleandu Data 12 februarie 2013 20:20:09
Problema Ograzi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>

#include <vector>
#include <iostream>
using namespace std;

#define MaxChar 1000000
#define verf ( (++CharB==MaxChar) ? ( cin.read(Buffer,MaxChar),CharB=0 ) : (1) )

long CharB=MaxChar-1;
char Buffer [ MaxChar ];

void cit ( int &a )
{
    bool ok=0;
    for ( ; !( (Buffer[ CharB ]>='0' && Buffer[ CharB ]<='9') || ( Buffer[ CharB ] == '-' ) ); verf )
        ;
    if ( Buffer[ CharB ] == '-' ){
        CharB++;
        ok=1;
    }
    for ( a=0; (Buffer[ CharB ]>='0' && Buffer[ CharB ]<='9'); a*=10,a+=( Buffer[ CharB ]-'0'), verf )
        ;
    if ( ok ){
        a=-a;
    }
}


#define MOD 1000003
#define max_n 50005

struct point {
	int x,y;
} Rectangle[ max_n ], sheep;

vector<int> Hash[ MOD ];

int n,m,w,h;
int i;

int get_value ( int x, int y ){
	int rez=0;
	rez = (x/w)*1469;
	rez += (y/h);
	rez %= MOD;
	return rez;
}

int main(){

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

	verf;

	cit ( n );
	cit ( m );
	cit ( w );
	cit ( h );
 //   scanf ("%d %d %d %d", &n, &m, &w, &h );
	for ( i=1; i<=n; ++i ){
//		scanf ("%d %d", &Rectangle[ i ].x, &Rectangle[ i ].y );
		cit ( Rectangle[ i ].x );
		cit ( Rectangle[ i ].y );
		int nr;
		nr = get_value ( Rectangle[ i ].x, Rectangle[ i ].y );
 		Hash[ nr ].push_back( i );
 		
		nr = get_value ( Rectangle[ i ].x + w, Rectangle[ i ].y + h);
 		Hash[ nr ].push_back( i );
		
		nr = get_value ( Rectangle[ i ].x + w, Rectangle[ i ].y );
 		Hash[ nr ].push_back( i );
		
		nr = get_value ( Rectangle[ i ].x, Rectangle[ i ].y + h);
 		Hash[ nr ].push_back( i );
		//printf("%d @ \n",nr);
	}
	int rez=0;
	for ( ; m; --m ){
//		scanf ("%d %d", &sheep.x, &sheep.y );
		cit ( sheep.x );
		cit ( sheep.y );
		int nr = get_value( sheep.x, sheep.y );
//		printf("%d @ \n",nr);
 		bool ok=0;
        for ( i=0; i< Hash[ nr ].size() && !ok; ++i ){
 			if ( sheep.x >= Rectangle[ Hash[ nr ][ i ] ].x &&
				sheep.x <= Rectangle[ Hash[ nr ][ i ] ].x + w &&
				sheep.y >= Rectangle[ Hash[ nr ][ i ] ].y &&
				sheep.y <= Rectangle[ Hash[ nr ][ i ] ].y + h )
				ok=1;
		}
		rez+=ok;
	}
	printf("%d\n",rez);
	return 0;
}