Pagini recente » Cod sursa (job #3161664) | Cod sursa (job #1366563) | Cod sursa (job #1256774) | Cod sursa (job #2956594) | Cod sursa (job #27372)
Cod sursa(job #27372)
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
#define MAXN 50005
#define MAXP 1000007
int x[MAXN], y[MAXN];
int r1, r2;
//impartim planu in dreptunghiuri HxW, formand un grid
//fiecarei ograzi va contine doar un singur punct in grid
//pentru ograzile cu coordonatele divizibile cu H, respectiv V luam punctul din stanga jos
int N, M, H, W;
vector<int> Mp[MAXP];
inline int hashPoint( pair<int, int> P )
{
return (int) (((long long)P.first * r1 + (long long)P.second * r2) % MAXP);
}
inline pair<int, int> getPoint( int id )
{
return make_pair( x[id] + (W - x[id] % W) % W, y[id] + (H - y[id] % H) % H);
}
int isin( int a, int b, int id )
{
return (x[id] <= a && a <= x[id] + W) && (y[id] <= b && b <= y[id] + H);
}
char tmp[16], *p;
int main()
{
srand( time(0) );
r1 = rand() % 2007;
r2 = rand() % 2007;
freopen("ograzi.in", "rt", stdin);
freopen("ograzi.out", "wt", stdout);
scanf("%d %d %d %d ", &N, &M, &W, &H);
for (int i = 0; i < N; i++)
{
fgets(tmp, 16, stdin);
for (p = tmp, x[i] = 0; '0' <= *p && *p <= '9'; p++)
x[i] = x[i] * 10 + *p - '0';
for (p++, y[i] = 0; '0' <= *p && *p <= '9'; p++)
y[i] = y[i] * 10 + *p - '0';
Mp[ hashPoint( getPoint(i) ) ].push_back(i);
}
int NR = 0;
for (; M; M--)
{
int a, b, A, B;
fgets(tmp, 16, stdin);
for (p = tmp, a = 0; '0' <= *p && *p <= '9'; p++)
a = a * 10 + *p - '0';
for (p++, b = 0; '0' <= *p && *p <= '9'; p++)
b = b * 10 + *p - '0';
if (a % W)
A = a - (a % W);
else
A = a - W;
if (b % H)
B = b - (b % H);
else
B = b - H;
int ok = 0;
for (int i = 0; i < 2 && !ok; i++)
for (int j = 0; j < 2 && !ok; j++)
{
int _A, _B;
_A = A + i * W;
_B = B + j * H;
int pct = hashPoint( make_pair(_A, _B) );
if (pct < 0)
continue;
for (size_t k = 0; k < Mp[ pct ].size() && !ok; k++)
if (isin(a, b, Mp[ pct ][k]))
ok = 1;
}
NR += ok;
}
printf("%d\n", NR);
return 0;
}