Cod sursa(job #749131)

Utilizator danalex97Dan H Alexandru danalex97 Data 15 mai 2012 20:57:38
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
#include<algorithm>

using namespace std;

pair<int, int> S[100002], D[100002];

int main()
{	
	ifstream q("grendizer.in");
	ofstream w("grendizer.out");
	
	int N, M,r,i, x,y,sol=0;
	q>>N>>M;
	
	for(i=0;i<N;++i)
	{		
		q>>x>>y;

		S[i]=make_pair(x+y,y);
		D[i]=make_pair(x-y,y);
	}
	
	sort(S,S + N);
	sort(D, D + N);
	
	pair<int,int> *i1,*i2;
	
	while( M-- )
	{	
		q>>x>>y>>r;     
		
		i1=lower_bound(S,S+N,make_pair(x+y-r,y-r));
		i2=upper_bound(S,S+N,make_pair(x+y-r,y));
        sol=i2-i1;
        
		i1=lower_bound(S,S+N,make_pair(x+y+r,y));
        i2=upper_bound(S,S+N,make_pair(x+y+r,y+r));
        sol+=i2-i1;
        
		i1=upper_bound(D,D+N,make_pair(x-y+r,y-r));
        i2=lower_bound(D,D+N,make_pair(x-y+r,y));
        sol+=i2-i1;
        
		i1=upper_bound(D,D+N,make_pair(x-y-r,y));
        i2=lower_bound(D,D+N,make_pair(x-y-r,y+r));
        sol+=i2-i1;
        
		w<<sol<<"\n";
   }
}