Cod sursa(job #255584)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 10 februarie 2009 00:26:31
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN  "grendizer.in"
#define OUT "grendizer.out"
#define N_MAX 1<<17

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

int N,M;
vector<pi> A,B;

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%d%d",&N,&M);
	
	int x,y;
	A.resize(N);
	B.resize(N--);
	
	FOR(i,0,N)
	{
		scanf("%d%d",&x,&y);
		A[i] = mp(x+y,x-y);
		B[i] = mp(x-y,x+y);
	}	
}

II void solve()
{
	sort(A.begin(),A.end() );
	sort(B.begin(),B.end() );
	
	int rez,x,y,r;	
	FOR(i,1,M)
	{
		rez = 0;
		scanf("%d%d%d\n",&x,&y,&r);
		
		rez += lower_bound(A.begin(),A.end(),mp(x+y+r,(x+r)-y)) - A.begin();
		rez -= upper_bound(A.begin(),A.end(),mp(x+y+r,x-(y+r)) ) - A.begin();
		rez += lower_bound(A.begin(),A.end(),mp(x-r+y,(x+r)-y)) - A.begin();
		rez -= upper_bound(A.begin(),A.end(),mp(x-r+y,x-(y+r)) ) - A.begin();
		
		rez += upper_bound(B.begin(),B.end(),mp(x-(y-r),x+y+r) ) - B.begin();
		rez -= lower_bound(B.begin(),B.end(),mp(x-(y-r),x-r+y)) - B.begin();
		rez += upper_bound(B.begin(),B.end(),mp(x-(y+r),x+y+r) ) - B.begin(); 
		rez -= lower_bound(B.begin(),B.end(),mp(x-(y+r),x-r+y)) - B.begin();
		
		printf("%d\n",rez);
	}	
}

int main()
{
	scan();
	solve();
	return 0;
}