Cod sursa(job #258154)

Utilizator savimSerban Andrei Stan savim Data 14 februarie 2009 19:51:20
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

#define MAX_N 100010

int n, m, x, y, sol, r;
pair <int, int> v1[MAX_N], v2[MAX_N];

int main() {

	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &x, &y);
		
		v1[i] = make_pair(x - y, y);
		v2[i] = make_pair(x + y, y);
	}
	
	sort(v1, v1 + n);
	sort(v2, v2 + n);
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &r);
		
		pair <int, int> *st = upper_bound(v1, v1 + n, make_pair(x - y + r, y - r));
		pair <int, int> *dr = upper_bound(v1, v1 + n, make_pair(x - y + r, y));
		sol = dr - st;
		
		st = lower_bound(v1, v1 + n, make_pair(x - y - r, y));
		dr = lower_bound(v1, v1 + n, make_pair(x - y - r, y + r));
		sol += dr - st;
		
		st = upper_bound(v2, v2 + n, make_pair(x + y - r, y - r));
		dr = upper_bound(v2, v2 + n, make_pair(x + y - r, y));
		sol += dr - st;
		
		st = lower_bound(v2, v2 + n, make_pair(x + y + r, y));
		dr = lower_bound(v2, v2 + n, make_pair(x + y + r, y + r));
		sol += dr - st;
		
		printf("%d\n", sol);
	}
	
	return 0;
}