Cod sursa(job #327661)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 29 iunie 2009 19:21:25
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

#define file_in "grendizer.in"
#define file_out "grendizer.out"

#define mp make_pair
#define Nmax 101001

pair<int,int> d1[Nmax],d2[Nmax];
pair<int,int> *it1,*it2;

int n,m,x,y,r,i,sol;

inline int abs(int a) { return a>=0?a:-a; }

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	
	for (i=1;i<=n;++i)
	{
		scanf("%d %d", &x,&y);
		d1[i]=mp(x-y,y);
		d2[i]=mp(x+y,y);
	}
	
	sort(d1+1,d1+n+1);
	sort(d2+1,d2+n+1);
	
	while(m--)
	{
		sol=0;
		scanf("%d %d %d", &x,&y,&r);
		
		it1=lower_bound(d1+1,d1+n+1,mp(x-y-r,y));
		it2=lower_bound(d1+1,d1+n+1,mp(x-y-r,y+r));
		
		sol+=abs(it2-it1);
		
		it1=upper_bound(d1+1,d1+n+1,mp(x-y+r,y-r));
		it2=upper_bound(d1+1,d1+n+1,mp(x-y+r,y));
		 
		sol+=abs(it2-it1);
		
		it1=lower_bound(d2+1,d2+n+1,mp(x+y-r,y-r));
		it2=lower_bound(d2+1,d2+n+1,mp(x+y-r,y));
		
		sol+=abs(it2-it1);
		
		it1=upper_bound(d2+1,d2+n+1,mp(x+y+r,y));
		it2=upper_bound(d2+1,d2+n+1,mp(x+y+r,y+r));
		 
		sol+=abs(it2-it1);
		
		printf("%d\n", sol);
		
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}