Cod sursa(job #847718)

Utilizator stoicatheoFlirk Navok stoicatheo Data 4 ianuarie 2013 13:37:41
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<algorithm>
 
using namespace std;
 
pair <int,int> s[100001],d[100001];
 
int main()
{
    int n,m,r,i,x,y,sol=0;
    pair <int,int> *it1,*it2;
 
    freopen("grendizer.in","r",stdin);
    freopen("grendizer.out","w",stdout);
 
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        s[i]=make_pair(x+y,y);
        d[i]=make_pair(x-y,y);
    }
 
    sort(s,s+n);
    sort(d,d+n);
 
    for (;m;--m)
    {
        scanf("%d%d%d",&x,&y,&r);
 
        it1=lower_bound(s,s+n,make_pair(x+y-r,y-r));
        it2=upper_bound(s,s+n,make_pair(x+y-r,y));
        sol=it2-it1;
 
        it1=lower_bound(s,s+n,make_pair(x+y+r,y));
        it2=upper_bound(s,s+n,make_pair(x+y+r,y+r));
        sol+=it2-it1;
 
        it1=upper_bound(d,d+n,make_pair(x-y+r,y-r));
        it2=lower_bound(d,d+n,make_pair(x-y+r,y));
        sol+=it2-it1;
 
        it1=upper_bound(d,d+n,make_pair(x-y-r,y));
        it2=lower_bound(d,d+n,make_pair(x-y-r,y+r));
        sol+=it2-it1;
 
        printf("%d\n",sol);
    }
    return 0;
}