Cod sursa(job #1018509)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 29 octombrie 2013 18:14:06
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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";
   }
}