Cod sursa(job #260732)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 17 februarie 2009 15:07:38
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define pii pair<int,int>
#define ff first
#define ss second
#define mp make_pair

const int maxN = 100100;
using namespace std;

pii Diag1[maxN], Diag2[maxN];
int N, M;

int main(){
    int i, a, b, Sol, r;
    pii *it1, *it2;

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

    scanf("%d%d", &N, &M);

    for (i = 1; i <= N; ++i){
        scanf("%d%d", &a, &b);
        Diag1[i] = mp(a + b, b);
        Diag2[i] = mp(a - b, b);
    }

    sort(Diag1 + 1, Diag1 + N + 1);
    sort(Diag2 + 1, Diag2 + N + 1);

    while ( M -- ){
        scanf("%d%d%d", &a, &b, &r);
        Sol = 0;
        // caut pe diagonala secundara partea din stanga jos a rombului cate puncte contine
        it1 = upper_bound(Diag1 + 1, Diag1 + N + 1, mp(a + b - r, b - r));
        it2 = upper_bound(Diag1 + 1, Diag1 + N + 1, mp(a + b - r, b));

        Sol += abs(it2 - it1);

        // caut pe diagonala secundara partea din dreapta sus a rombului cate puncte contine
        it1 = lower_bound(Diag1 + 1, Diag1 + N + 1, mp(a + r + b, b));
        it2 = lower_bound(Diag1 + 1, Diag1 + N + 1, mp(a + r + b, b + r));

        Sol += abs(it2 - it1);

        // caut pe diagonala principala partea in stanga sus a rombului cate puncte contine

        it1 = upper_bound(Diag2 + 1, Diag2 + N + 1, mp(a - b - r, b));
        it2 = upper_bound(Diag2 + 1, Diag2 + N + 1, mp(a - b - r, b + r));

        Sol += abs(it2 - it1);

        // caut pe diagonala principala partea in dreapta jos a rombului cate puncte contine

        it1 = lower_bound(Diag2 + 1, Diag2 + N + 1, mp(a - b + r, b - r));
        it2 = lower_bound(Diag2 + 1, Diag2 + N + 1, mp(a - b + r, b));

        Sol += abs(it2 - it1);

        printf("%d\n", Sol);
    }
}