Cod sursa(job #1662269)

Utilizator Athena99Anghel Anca Athena99 Data 24 martie 2016 17:07:59
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <algorithm>
#include <fstream>

using namespace std;

ifstream fin("grendizer.in");
ofstream fout("grendizer.out");

const int nmax= 100000;

int n, n2, m;

struct str {
    int x, y;
} v[2][nmax+1];

inline str mp( int x, int y ) {
    str sol;
    sol.x= x, sol.y= y;

    return sol;
}

bool cmp( str x, str y ) {
    if ( x.x==y.x )
        return x.y<y.y;
    return x.x<y.x;
}

int bsearch( int k, int x, int y ) {
    int ans= 0;
    for ( int step= n2; step>0; step/= 2 ) {
        if ( ans+step<=n && cmp(mp(x, y), v[k][ans+step])==0 ) {
            ans+= step;
        }
    }

    return ans;
}

int main(  ) {
    fin>>n>>m;
    for ( n2= 1; n2<=n; n2*= 2 ) ;
    for ( int i= 1; i<=n; ++i ) {
        int x, y;
        fin>>x>>y;
        v[0][i].x= x+y, v[0][i].y= y;
        v[1][i].x= y-x, v[1][i].y= y;
    }

    sort( v[0]+1, v[0]+n+1, cmp );
    sort( v[1]+1, v[1]+n+1, cmp );

    for ( int cnt= 1; cnt<=m; ++cnt ) {
        int x, y, r;
        fin>>x>>y>>r;

        int sol= 0;
        sol= sol+bsearch(0, x+y-r, y)-bsearch(0, x+y-r, y-r);
        sol= sol+bsearch(1, y-x-r, y-1)-bsearch(1, y-x-r, y-r-1);
        sol= sol+bsearch(1, y-x+r, y+r)-bsearch(1, y-x+r, y);
        sol= sol+bsearch(0, x+y+r, y+r-1)-bsearch(0, x+y+r, y-1);

        fout<<sol<<"\n";
    }

    return 0;
}