Cod sursa(job #407926)

Utilizator freak93Adrian Budau freak93 Data 2 martie 2010 18:46:03
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="grendizer.in";
const char oname[]="grendizer.out";
const int maxn=100005;

ifstream f(iname);
ofstream g(oname);

pair<int,int> dp[maxn],ds[maxn];

bool operator<=(const pair<int,int> &a,const pair<int,int> &b)
{
    if(a.first==b.first)
        return a.second<=b.second;
    return a.first<=b.first;
}

int bs(pair<int,int> *a,const int &n,const pair<int,int> &x)
{
    int step,i;
    for(step=1;step<n;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=n&&a[i+step]<=x)
            i+=step;
    return i;
}

int n,i,x,y,m,k,r;

int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>x>>y,dp[i].first=x+y,dp[i].second=y,ds[i].first=y-x,ds[i].second=y;

    sort(dp+1,dp+n+1);
    sort(ds+1,ds+n+1);

    for(i=1;i<=m;++i)
    {
        f>>x>>y>>r;
        k=0;
        k+=bs(dp,n,make_pair(x+y-r,y))-bs(dp,n,make_pair(x+y-r,y-r));//stanga sus
        k+=bs(ds,n,make_pair(y-x+r,y+r))-bs(ds,n,make_pair(y-x+r,y));//dreapta sus
        k+=bs(dp,n,make_pair(x+y+r,y+r-1))-bs(dp,n,make_pair(x+y+r,y-1));//dreapta jos
        k+=bs(ds,n,make_pair(y-x-r,y-1))-bs(ds,n,make_pair(y-x-r,y-r-1));//stanga jos;
        g<<k<<"\n";
    }

    f.close();
    g.close();

    return 0;
}