Cod sursa(job #518974)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 3 ianuarie 2011 17:49:00
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#define mp make_pair
#define pii pair <int,int>
#define NMAX 100005
using namespace std;
int n,m;
pii A[NMAX],B[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		A[i]=mp(x+y,y);
		B[i]=mp(x-y,y);
	}
	sort(A+1,A+n+1);
	sort(B+1,B+n+1);
}
void solve()
{
	int i,x,y,r,rez;
	pii *it1,*it2;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d%d",&x,&y,&r);
		rez=0;
		
		it1=lower_bound(A+1,A+n+1,mp(x+y-r,y-r));
		it2=upper_bound(A+1,A+n+1,mp(x+y-r,y));
		rez+=it2-it1;

		it1=lower_bound(A+1,A+n+1,mp(x+y+r,y));
		it2=upper_bound(A+1,A+n+1,mp(x+y+r,y+r));
		rez+=it2-it1;

		it1=upper_bound(B+1,B+n+1,mp(x-y-r,y));
		it2=lower_bound(B+1,B+n+1,mp(x-y-r,y+r));
		rez+=it2-it1;

		it1=upper_bound(B+1,B+n+1,mp(x-y+r,y-r));
		it2=lower_bound(B+1,B+n+1,mp(x-y+r,y));
		rez+=it2-it1;

		printf("%d\n",rez);
	}
}
int main()
{
	freopen("grendizer.in","r",stdin);
	freopen("grendizer.out","w",stdout);
	read();
	solve();
	return 0;
}