Cod sursa(job #268555)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 1 martie 2009 13:52:15
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#include <set>
#include <algorithm>

#define maxn 100010
#define mp make_pair

using namespace std;

long n, i, j, k, m, x, y, r, sol;
pair<long, long> d1[maxn], d2[maxn];

int main()
{
    freopen("grendizer.in", "r", stdin);
    freopen("grendizer.out", "w", stdout);
    scanf("%d %d\n", &n, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d", &x, &y);
        d1[i]=mp(x-y, y);
        d2[i]=mp(x+y, y);
    }
    sort(d1+1, d1+n+1);
    sort(d2+1, d2+n+1);
    pair<long, long> *st, *dr;
    for(; m; m--)
    {
        scanf("%d %d %d\n", &x, &y, &r);
        sol=0;
        st=upper_bound(d1+1, d1+n+1, mp(x-y+r, y-r));
        dr=upper_bound(d1+1, d1+n+1, mp(x-y+r, y));
        sol+=dr-st;
        st=lower_bound(d1+1, d1+n+1, mp(x-y-r, y));
        dr=lower_bound(d1+1, d1+n+1, mp(x-y-r, y+r));
        sol+=dr-st;
        st=lower_bound(d2+1, d2+n+1, mp(x+y-r, y-r));
        dr=lower_bound(d2+1, d2+n+1, mp(x+y-r, y));
        sol+=dr-st;
        st=upper_bound(d2+1, d2+n+1, mp(x+y+r, y));
        dr=upper_bound(d2+1, d2+n+1, mp(x+y+r, y+r));
        sol+=dr-st;
        printf("%d\n", sol);
    }
    return 0;
}