Pagini recente » Cod sursa (job #1759507) | Cod sursa (job #3248925) | Cod sursa (job #1892977) | Cod sursa (job #345446) | Cod sursa (job #715606)
Cod sursa(job #715606)
#include <fstream>
#include <vector>
using namespace std;
const char InFile[]="ograzi.in";
const char OutFile[]="ograzi.out";
const int HASH_MOD=666013;
const int dx[]={0,0,1,1};
const int dy[]={1,0,1,0};
const int MaxN=50111;
ifstream fin(InFile);
ofstream fout(OutFile);
struct Point
{
int x,y;
};
int N,M,W,H,x,y,sol;
vector<int> Hash[HASH_MOD];
Point V[MaxN];
inline int HashFunc(const int &x, const int &y)
{
return (x*211+y*307)%HASH_MOD;
}
inline bool PointInRectangle(const int &px, const int &py, const int &x1, const int &y1, const int &x2, const int &y2)
{
if(px<x1)
{
return false;
}
if(x2<px)
{
return false;
}
if(py<y1)
{
return false;
}
if(y2<py)
{
return false;
}
return true;
}
inline bool HashFound(const int &px, const int &py)
{
int key=HashFunc(px,py);
for(vector<int>::iterator it=Hash[key].begin();it!=Hash[key].end();++it)
{
if(PointInRectangle(x,y,V[*it].x,V[*it].y,V[*it].x+W,V[*it].y+H))
{
return true;
}
}
return false;
}
int main()
{
fin>>N>>M>>W>>H;
for(register int i=1;i<=N;++i)
{
fin>>x>>y;
V[i].x=x;
V[i].y=y;
int px=(int)((x+W-0.5)/W),py=(int)((y+H-0.5)/H);
Hash[HashFunc(px,py)].push_back(i);
}
for(register int i=1;i<=M;++i)
{
fin>>x>>y;
int px=(int)((x-0.5)/W),py=(int)((y-0.5)/H);
for(register int d=0;d<4;++d)
{
if(HashFound(px+dx[d],py+dy[d]))
{
++sol;
break;
}
}
}
fin.close();
fout<<sol;
fout.close();
return 0;
}