Pagini recente » Cod sursa (job #1678133) | Cod sursa (job #2689804) | Cod sursa (job #3271619) | Cod sursa (job #1553135) | Cod sursa (job #2639943)
#include <fstream>
#include <algorithm>
#include <queue>
#include <random>
#include <chrono>
using namespace std;
ifstream cin ("ograzi.in");
ofstream cout ("ograzi.out");
struct Point {
int x, y;
bool operator < (const Point &other) const {
return (x < other.x || (x == other.x && y < other.y));
}
};
int n, m, w, h, passed;
Point v[50005], a[100005];
int aib[1000005];
queue <int> q;
int lsb(int n) {
return n & -n;
}
void update(int ind, int val) {
for(; ind <= 1000001; ind += lsb(ind))
aib[ind] += val;
}
int query(int ind) {
int ans = 0;
for(; ind; ind -= lsb(ind))
ans += aib[ind];
return ans;
}
void buildTest() {
unsigned t = chrono :: system_clock :: now().time_since_epoch().count();
mt19937 gen(t);
uniform_int_distribution <int> N(1, 10), dist(0, 1000);
n = N(gen), m = N(gen);
w = dist(gen), h = dist(gen);
for(int i = 1; i <= n; i++)
v[i].x = dist(gen), v[i].y = dist(gen);
for(int i = 1; i <= m; i++)
a[i].x = dist(gen), a[i].y = dist(gen);
}
int brut() {
int ans = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(v[j].x <= a[i].x && a[i].x <= v[j].x + w && v[j].y <= a[i].y && a[i].y <= v[j].y + h) {
ans++;
break;
}
}
}
return ans;
}
void solve() {
cin >> n >> m >> w >> h;
for(int i = 1; i <= n; i++)
cin >> v[i].x >> v[i].y;
for(int i = 1; i <= m; i++)
cin >> a[i].x >> a[i].y;
for(int i = 1; i <= n; i++)
v[i].x++, v[i].y++;
for(int j = 1; j <= m; j++)
a[j].x++, a[j].y++;
sort(v + 1, v + n + 1);
sort(a + 1, a + m + 1);
int j = 1, ans = 0;
while(!q.empty())
q.pop();
for(int i = 1; i <= 1000001; i++)
aib[i] = 0;
for(int i = 1; i <= m; i++) {
while(j <= n && v[j].x + w < a[i].x)
j++;
while(j <= n && v[j].x <= a[i].x && a[i].x <= v[j].x + w)
q.push(j), update(v[j].y, 1), j++;
while(!q.empty() && v[q.front()].x + w < a[i].x)
update(v[q.front()].y, -1), q.pop();
ans += (query(a[i].y) > query(a[i].y - h));
}
/*int x = brut();
if(ans == x)
cout << "Accepted!", passed++;
else
cout << "Wrong Answer!";*/
cout << ans << "\n";
}
void tester() {
for(int t = 1; t <= 10; t++) {
cout << "Running test #" << t << "....\n";
buildTest();
solve();
}
cout << "Passed " << passed << " / 10 test. Good job!\n";
}
int main() {
// tester();
solve();
return 0;
}