Cod sursa(job #2026455)

Utilizator giotoPopescu Ioan gioto Data 24 septembrie 2017 14:23:21
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
pair <int, int> s[100005], d[100005];
int main()
{
    freopen("grendizer.in", "r", stdin);
    freopen("grendizer.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int x, y, r;
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &x, &y);
        s[i] = make_pair(x + y, y);
        d[i] = make_pair(x - y, y);
    }
    sort(s + 1, s + n + 1);
    sort(d + 1, d + n + 1);
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &x, &y, &r);
        int cnt = 0;
        pair <int, int> *it1, *it2;
        it1 = upper_bound(s + 1, s + n + 1, make_pair(x + y + r, y));
        it2 = upper_bound(s + 1, s + n + 1, make_pair(x + y + r, y + r));
        cnt = cnt + it2 - it1;
        it1 = lower_bound(s + 1, s + n + 1, make_pair(x + y - r, y - r));
        it2 = lower_bound(s + 1, s + n + 1, make_pair(x + y - r, y));
        cnt = cnt + it2 - it1;
        it1 = lower_bound(d + 1, d + n + 1, make_pair(x - y - r, y));
        it2 = lower_bound(d + 1, d + n + 1, make_pair(x - y - r, y + r));
        cnt = cnt + it2 - it1;
        it1 = upper_bound(d + 1, d + n + 1, make_pair(x - y + r, y - r));
        it2 = upper_bound(d + 1, d + n + 1, make_pair(x - y + r, y));
        cnt = cnt + it2 - it1;
        printf("%d\n", cnt);
    }
    return 0;
}