Cod sursa(job #253311)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 17:40:37
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
 #include <fstream>  
 #include <vector>  
 using namespace std;  
   
 const int MAX_HASH = 666013;  
   
 int N, M, W, H;  
 vector < pair < pair <int, int>, pair <int, int> > > hash[MAX_HASH];  
   
 inline int h(const pair <int, int> &A)  
 {  
     return (((long long) A.first << 20) + A.second) % MAX_HASH;  
 }  
   
 inline void insert_hash(const pair < pair <int, int>, pair <int, int> > &P)  
 {  
     int key = h(P.first);  
     hash[key].push_back(P);  
 }  
   
 bool find_hash(const pair <int, int> &pos, const pair <int, int> point)  
 {  
     int key = h(pos);  
     for(size_t i = 0; i < hash[key].size(); ++i)  
         if(hash[key][i].first == pos)  
             return hash[key][i].second.first <= point.first  
                 && hash[key][i].second.first + W >= point.first  
                 && hash[key][i].second.second <= point.second  
                 && hash[key][i].second.second + H >= point.second;  
     return false;  
 }  
   
   
 int main()  
 {  
     ifstream in("ograzi.in");  
     ofstream out("ograzi.out");  
   
     int x, y, cnt = 0, px, py;  
     in >> N >> M >> W >> H;  
     for(int i = 0; i < N; ++i)  
     {  
         in >> x >> y;  
         insert_hash(make_pair(make_pair((2 * x - 1) / (2 * W), (2 * y - 1) / (2 * H)), make_pair(x, y)));  
     }  
     for(int i = 0; i < M; ++i)  
     {  
         in >> x >> y;  
         px = (2 * x - 1) / (2 * W);  
         py = (2 * y - 1) / (2 * H);  
         cnt += find_hash(make_pair(px, py), make_pair(x, y))  
             || (px > 0 && find_hash(make_pair(px - 1, py), make_pair(x, y)))  
             || (py > 0 && find_hash(make_pair(px, py - 1), make_pair(x, y)))  
             || (px > 0 && py > 0 && find_hash(make_pair(px - 1, py - 1), make_pair(x, y)));  
     }  
   
     out << cnt << endl;  
   
     return 0;  
}