Cod sursa(job #257474)

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

#define ub upper_bound
#define lb lower_bound
#define mp make_pair

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] = mp(x + y, y), b[i] = mp(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 = ub(a, a + n, mp(x + y - r, y)) - ub(a, a + n, mp(x + y - r, y - r));
		sol += lb(a, a + n, mp(x + y + r, y + r)) - lb(a, a + n, mp(x + y + r, y));
		sol += ub(b, b + n, mp(x - y - r, y + r)) - ub(b, b + n, mp(x - y - r, y));
        sol += lb(b, b + n, mp(x - y + r, y)) - lb(b, b + n, mp(x - y + r, y - r));
    }
}