Cod sursa(job #1504985)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 18 octombrie 2015 17:03:42
Problema Grendizer Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <algorithm>

#define NMAX 100007

using namespace std;

pair < int, int > s[NMAX], d[NMAX];
pair < int, int > *it1, *it2;

int main(){
    int n, m, r, x, y, Ans = 0;
    freopen("grendizer.in","r",stdin);
    freopen("grendizer.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        int x, y;
        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(int i = 1; i <= m; ++i){
        int x, y, r;
        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));
        Ans = 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));
        Ans += 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));
        Ans += 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));
        Ans += it2 - it1;
        printf("%d\n",Ans);
    }
    return 0;
}