Cod sursa(job #475640)

Utilizator DraStiKDragos Oprica DraStiK Data 7 august 2010 19:56:14
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair

vector <pair <int,int> > vpoz,vneg;
int n,m;

void read ()
{
    int i,x,y;

    scanf ("%d%d",&n,&m);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d",&x,&y);
        vpoz.pb (mp (x+y,y));
        vneg.pb (mp (x-y,y));
    }
}

void solve ()
{
    vector <pair <int,int> > :: iterator it1,it2;
    int i,x,y,r,nrc;

    sort (vpoz.begin (),vpoz.end ());
    sort (vneg.begin (),vneg.end ());
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d%d",&x,&y,&r);
        it1=lower_bound (vpoz.begin (),vpoz.end (),mp (x+y-r,y-r));
        it2=upper_bound (vpoz.begin (),vpoz.end (),mp (x+y-r,y));
        nrc=it2-it1;
        it1=lower_bound (vpoz.begin (),vpoz.end (),mp (x+y+r,y));
        it2=upper_bound (vpoz.begin (),vpoz.end (),mp (x+y+r,y+r));
        nrc+=it2-it1;
        it1=upper_bound (vneg.begin (),vneg.end (),mp (x-y+r,y-r));
        it2=lower_bound (vneg.begin (),vneg.end (),mp (x-y+r,y));
        nrc+=it2-it1;
        it1=upper_bound (vneg.begin (),vneg.end (),mp (x-y-r,y));
        it2=lower_bound (vneg.begin (),vneg.end (),mp (x-y-r,y+r));
        nrc+=it2-it1;
        printf ("%d\n",nrc);
    }
}

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

    read ();
    solve ();

    return 0;
}