Cod sursa(job #257492)

Utilizator gicagica popescu gica Data 13 februarie 2009 14:06:18
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>  
#include <algorithm>  
#define maxn 100010  
  
using namespace std;  
  
int n, i, j, sol, x, y, r, m;  
pair <int,int> v[maxn], z[maxn];  
pair <int,int> *it1, *it2;  
  
int main() {  
    freopen("grendizer.in", "r", stdin);  
    freopen("grendizer.out", "w", stdout);  
      
    scanf("%d%d", &n, &m);  
    for (i = 1; i <= n; i++) {  
        scanf("%d%d", &x, &y);  
        v[i] = make_pair(x + y, y);  
        z[i] = make_pair(x - y, y);  
    }  
      
    sort(v + 1, v + n + 1);  
    sort(z + 1, z + n + 1);  
      
    for (i = 1; i <= m; i++) {  
          
        scanf("%d%d%d", &x, &y, &r);  
         
		it1 = lower_bound(v + 1, v + n + 1, make_pair(x + y + r, y + r));
		it2 = lower_bound(v + 1, v + n + 1, make_pair(x + y + r, y));
        sol = it1 - it2;  
          
        it1 = upper_bound(v + 1, v + n + 1, make_pair(x + y - r, y));  
        it2 = upper_bound(v + 1, v + n + 1, make_pair(x + y - r, y - r));  
        sol += it1 - it2;  
  
        it1 = lower_bound(z + 1, z + n + 1, make_pair(x - y + r, y));  
        it2 = lower_bound(z + 1, z + n + 1, make_pair(x - y + r, y - r));  
        sol += it1 - it2;  
  
        it1 = upper_bound(z + 1, z + n + 1, make_pair(x - y - r, y + r));  
        it2 = upper_bound(z + 1, z + n + 1, make_pair(x - y - r, y));  
        sol += it1 - it2;  
          
        printf("%d\n", sol);  
    }  
      
    return 0;  
}