Cod sursa(job #465083)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 23 iunie 2010 11:50:05
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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";}
return 0;}