Cod sursa(job #2580614)

Utilizator betybety bety bety Data 13 martie 2020 20:01:18
Problema Grendizer Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <fstream>

#include <algorithm>

#define nmax 100002

using namespace std;

ifstream fin("grendizer.in");

ofstream fout("grendizer.out");



int n,m;

int x,y,r;

struct pct

{

    int x,y;

}v1[nmax],v2[nmax];



bool cmpPlus(pct a,pct b)

{

    return (a.x+a.y<b.x+b.y || (a.x+a.y==b.x+b.y && a.y<b.y));

}



bool cmpMinus(pct a,pct b)

{

    return (a.x-a.y<b.x-b.y || (a.x-a.y==b.x-b.y && a.y<b.y));

}



int binPlus(int r,int a,int b)

{

    int st=1,dr=n,sol1=-1,sol2=-1;

    while(st<=dr)

    {

        int mij=(st+dr)/2;

        if(v1[mij].x+v1[mij].y<r)

            st=mij+1;

        else if(v1[mij].x+v1[mij].y>r)

            dr=mij-1;

        else

        {

            if(v1[mij].y<a)st=mij+1;

            else

            {

                sol1=mij;

                dr=mij-1;

            }

        }

    }



    st=1,dr=n;

    while(st<=dr)

    {

        int mij=(st+dr)/2;

        if(v1[mij].x+v1[mij].y<r)

            st=mij+1;

        else if(v1[mij].x+v1[mij].y>r)

            dr=mij-1;

        else

        {

            if(v1[mij].y>b)dr=mij-1;

            else

            {

                sol2=mij;

                st=mij+1;

            }

        }

    }

    if(sol1>0 && sol2>0)

        return sol2-sol1+1;

    return 0;

}



int binMinus(int r,int a,int b)

{

    int st=1,dr=n,sol1=-1,sol2=-1;

    while(st<=dr)

    {

        int mij=(st+dr)/2;

        if(v2[mij].x-v2[mij].y<r)

            st=mij+1;

        else if(v2[mij].x-v2[mij].y>r)

            dr=mij-1;

        else

        {

            if(v2[mij].y<a)st=mij+1;

            else

            {

                sol1=mij;

                dr=mij-1;

            }

        }

    }



    st=1,dr=n;

    while(st<=dr)

    {

        int mij=(st+dr)/2;

        if(v2[mij].x-v2[mij].y<r)

            st=mij+1;

        else if(v2[mij].x-v2[mij].y>r)

            dr=mij-1;

        else

        {

            if(v2[mij].y>b)dr=mij-1;

            else

            {

                sol2=mij;

                st=mij+1;

            }

        }

    }

    if(sol1>0 && sol2>0)

        return sol2-sol1+1;

    return 0;

}



int main()

{

    fin>>n>>m;

    for(int i=1;i<=n;i++)

    {

        fin>>x>>y;

        v1[i].x=v2[i].x=x;

        v1[i].y=v2[i].y=y;

    }

    sort(v1+1,v1+n+1,cmpPlus);

    sort(v2+1,v2+n+1,cmpMinus);



    for(int i=1;i<=m;i++)

    {

        fin>>x>>y>>r;



        int ans=0;



        ans+=binPlus(x+y-r,y-r,y);

        ans+=binPlus(x+y+r,y,y+r);

        ans+=binMinus(x-y+r,y-r+1,y-1);

        ans+=binMinus(x-y-r,y+1,y+r-1);



        fout<<ans<<"\n";

    }



    return 0;
}