Cod sursa(job #257488)

Utilizator CezarMocanCezar Mocan CezarMocan Data 13 februarie 2009 13:59:14
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <algorithm>
#define maxn 100010

using namespace std;

int n, i, j, sol, x, y, r, m;
pair <int,int> v[maxn], z[maxn];
pair <int,int> *it1, *it2;

int main() {
	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &x, &y);
		v[i] = make_pair(x + y, x);
		z[i] = make_pair(x - y, x);
	}
	
	sort(v + 1, v + n + 1);
	sort(z + 1, z + n + 1);
	
	for (i = 1; i <= m; i++) {
		
		scanf("%d%d%d", &x, &y, &r);
		sol = 0;
		
		it1 = lower_bound(v + 1, v + n + 1, make_pair(x + y + r, x + r));
		it2 = lower_bound(v + 1, v + n + 1, make_pair(x + y + r, x));
		sol += abs(it2 - it1);
		
		it1 = upper_bound(v + 1, v + n + 1, make_pair(x + y - r, x));
		it2 = upper_bound(v + 1, v + n + 1, make_pair(x + y - r, x - r));
		sol += abs(it1 - it2);

		it1 = lower_bound(z + 1, z + n + 1, make_pair(x - y + r, x));
		it2 = lower_bound(z + 1, z + n + 1, make_pair(x - y + r, x + r));
		sol += abs(it2 - it1);

		it1 = upper_bound(z + 1, z + n + 1, make_pair(x - y - r, x - r));
		it2 = upper_bound(z + 1, z + n + 1, make_pair(x - y - r, x));
		sol += abs(it1 - it2);
		
		printf("%d\n", sol);
	}
	
	return 0;
}