Cod sursa(job #838733)

Utilizator stoicatheoFlirk Navok stoicatheo Data 20 decembrie 2012 13:56:46
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <vector>
using namespace std;
 
const int Pars = 2500010;
const int Hsize = 193939;
const int Hsexion = 97;
 
ifstream F("ograzi.in");
ofstream G("ograzi.out");
 
char Str[Pars];int Act;
 
void Get(int& A)
{
    while ( Str[Act]<'0' || Str[Act]>'9' ) ++Act;
    while ( Str[Act]>='0' && Str[Act]<='9' ) A=A*10+Str[Act++]-'0';
}
 
int N,M,W,H,Rez;
 
#define x first
#define y second
 
typedef pair<int,int> Pair;
typedef vector< Pair >::iterator Iter;
vector< Pair > Hash[Hsize];
 
inline int Hashing(int a,int b)
{   return (a*Hsexion+b)%Hsize; }
 
int Find(int a,int b,int A,int B)
{
    int Place = Hashing(a,b);
    for ( Iter it=Hash[Place].begin();it!=Hash[Place].end();++it)
        if ( (it->x)<=A && (it->x)+W>=A && (it->y)<=B && (it->y)+H>=B )
            return 1;
    return 0;
}
 
int main()
{
    F.getline(Str,Pars,EOF);
     
    Get(N), Get(M);
    Get(W), Get(H);
     
    for (int i=1;i<=N;++i)
    {
        int x=0, y=0;
        Get(x), Get(y);
         
        int a=(x+W-1)/W;
        int b=(y+H-1)/H;
         
        Hash[ Hashing( a , b ) ].push_back( make_pair(x,y) );
    }
     
    while ( M-- )
    {
        int  A=0 , B=0;
        Get(A), Get(B);
         
        int a=(A+W-1)/W;
        int b=(B+H-1)/H;
         
        Rez+= Find(a,b,A,B) | Find(a,b-1,A,B) | Find(a-1,b,A,B) | Find(a-1,b-1,A,B) ;
    }       
     
    G<<Rez<<'\n';
}