Cod sursa(job #572686)

Utilizator SpiderManSimoiu Robert SpiderMan Data 5 aprilie 2011 15:47:47
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
# include <algorithm>
# include <cstdio>
using namespace std ;

# define lb(A, x, y) lower_bound ( A + 1, A + N + 1, make_pair ( x, y ) )
# define ub(A, x, y) upper_bound ( A + 1, A + N + 1, make_pair ( x, y ) )
# define sr(A)       sort ( A + 1, A + N + 1 )

const char *FIN = "grendizer.in", *FOU = "grendizer.out" ;

pair < int, int > A[100005], B[100005] ;
int N, M ;

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    scanf ( "%d %d", &N, &M ) ;
    for ( int i = 1, x, y ; i <= N; ++i ) {
        scanf ( "%d %d", &x, &y ) ;
        A[i] = make_pair ( x + y, y ) ;
        B[i] = make_pair ( x - y, y ) ;
    }
    sr(A), sr(B) ;

    for ( int x, y, r ; M; --M ) {
        scanf ( "%d %d %d", &x, &y, &r ) ;
        printf ( "%d\n", ub(A, x + y - r, y) - lb (A, x + y - r, y - r) + ub(A, x + y + r, y + r) - lb(A, x + y + r, y) +
                 lb (B, x - y - r, y + r) - ub (B, x - y - r, y) + lb (B, x - y + r, y) - ub (B, x - y + r, y - r) ) ;
    }
}