Cod sursa(job #371891)

Utilizator FlorianFlorian Marcu Florian Data 7 decembrie 2009 18:14:27
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
using namespace std;
#include<fstream>
#include<algorithm>
#define MAX_N 100002
#define mp make_pair
pair<int, int> S[MAX_N], D[MAX_N];
int main()
{
	ifstream f("grendizer.in");
	ofstream g("grendizer.out");
	int N, M,r,i, x,y,sol = 0;
	f>>N>>M;
	for(i=0;i<N;++i)
	{
		f>>x>>y;
		S[i] = mp(x+y, y);
		D[i] = mp(x-y, y);
	}
	sort(S,S + N); sort(D, D + N);
	pair<int,int> *i1,*i2;
	while(M--)
	{
		f>>x>>y>>r;
		i1 = lower_bound(S,S+N,mp(x+y-r, y-r));
		i2 = upper_bound(S,S+N,mp(x+y-r, y));
		sol = i2-i1;
		i1 = lower_bound(S,S+N,mp(x+y+r, y));
		i2 = upper_bound(S,S+N,mp(x+y+r, y+r));
		sol += i2-i1;
		i1 = upper_bound(D,D+N,mp(x-y+r, y-r));
		i2 = lower_bound(D,D+N,mp(x-y+r, y));
		sol += i2-i1;
		i1 = upper_bound(D,D+N,mp(x-y-r, y));
		i2 = lower_bound(D,D+N,mp(x-y-r, y+r));
		sol += i2-i1;
		g<<sol<<"\n";
	}
	return 0;
}