Cod sursa(job #255320)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 9 februarie 2009 01:51:47
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 100010
#define pct pair <int, int>
#define mp make_pair

int N, M, Sol;
pct A[MAXN], B[MAXN];

int main()
{
	freopen("grendizer.in", "r", stdin);
	freopen("grendizer.out", "w", stdout);

	int i, x, y, R;
	pct *I, *J;

	scanf("%d %d ", &N, &M);

	for (i = 0; i < N; i++)
	{
		scanf("%d %d ", &x, &y);
		A[i] = mp(x+y, y);
		B[i] = mp(x-y, y);
	}

	sort(A, A+N);
	sort(B, B+N);

	for (i = 1; i <= M; i++)
	{
		scanf("%d %d %d ", &x, &y, &R);

		I = upper_bound(A, A+N, mp(x+y-R, y));
		J = upper_bound(A, A+N, mp(x+y-R, y-R));
		Sol = I - J;

		I = lower_bound(B, B+N, mp(x-y+R, y));
		J = lower_bound(B, B+N, mp(x-y+R, y-R));
		Sol += I - J;

		I = lower_bound(A, A+N, mp(x+y+R, y+R));
		J = lower_bound(A, A+N, mp(x+y+R, y));
		Sol += I - J;
		
		I = upper_bound(B, B+N, mp(x-y-R, y+R));
		J = upper_bound(B, B+N, mp(x-y-R, y));
		Sol += I - J;

		printf("%d\n", Sol);
	}

	return 0;
}