Cod sursa(job #257472)

Utilizator raduzerRadu Zernoveanu raduzer Data 13 februarie 2009 13:26:05
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;

int n, m, sol, x, y, r;
pair <int, int> a[MAX_N], b[MAX_N];

int main()
{
    freopen("grendizer.in", "r", stdin);
    freopen("grendizer.out", "w", stdout);

    scanf("%d %d ", &n, &m);

    for (int i = 0; i < n; a[i] = make_pair(x + y, y), b[i] = make_pair(x - y, y), i++)
        scanf("%d %d ", &x, &y);

    sort(a, a+n);
    sort(b, b+n);

    for (; m; printf("%d\n", sol), --m)
    {
        scanf("%d %d %d ", &x, &y, &r);

        sol = upper_bound(a, a + n, make_pair(x + y - r, y)) - upper_bound(a, a + n, make_pair(x + y - r, y - r));
		sol += lower_bound(a, a + n, make_pair(x + y + r, y + r)) - lower_bound(a, a + n, make_pair(x + y + r, y));
		sol += upper_bound(b, b + n, make_pair(x - y - r, y + r)) - upper_bound(b, b + n, make_pair(x - y - r, y));
        sol += lower_bound(b, b + n, make_pair(x - y + r, y)) - lower_bound(b, b + n, make_pair(x - y + r, y - r));
    }
}