Cod sursa(job #877676)

Utilizator veleanduAlex Velea veleandu Data 13 februarie 2013 01:37:14
Problema Ograzi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
 
#include <vector>
#include <iostream>
#include <fstream>
using namespace std;
 
#define MaxChar 1000000
#define verf ( (++CharB==MaxChar) ? ( in.read(Buffer,MaxChar),CharB=0 ) : (1) )
 
ifstream in("ograzi.in");
ofstream out("ograzi.out");
 
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 1048583
#define max_n 50005
 
struct point {
    int x,y;
} sheep, rectangle;
 
vector<point> Hash[ MOD ];
 
int n,m,w,h;
int i,d;
 
int dx[4] = { 0, -1, -1,  0 };
int dy[4] = { 0,  0, -1, -1 };

int get_value ( int x, int y ){
	if ( x < 0 || y < 0 )
		return -1;
    return (1LL*x*100001 + y ) % MOD;
}
 
int main(){
    verf;
    cit ( n );    cit ( m );    cit ( w );    cit ( h );
    for ( i=1; i<=n; ++i ){
        cit ( rectangle.x );	cit ( rectangle.y );
        int nr;
        nr = get_value ( rectangle.x/w , rectangle.y/h );
		Hash[ nr ].push_back ( rectangle );
    }
    int rez=0;
    for ( ; m; --m ){
        cit ( sheep.x );
        cit ( sheep.y );
        bool ok=0;
		for ( d=0; d<4; ++d ){
			int nr = get_value ( sheep.x/w + dx[ d ] , sheep.y/h + dy[ d ] );
			if ( nr != -1 ){
		        for ( i=0; i< int ( Hash[ nr ].size() ) && !ok; ++i ){
		            if ( sheep.x >= Hash[ nr ][ i ].x &&
		                sheep.x <= Hash[ nr ][ i ].x + w &&
		                sheep.y >= Hash[ nr ][ i ].y &&
		                sheep.y <= Hash[ nr ][ i ].y + h )
		                ok=1;
		        }
			}
		}
        rez+=ok;
    }
    out<<rez;
    return 0;
}