Cod sursa(job #2558876)

Utilizator As932Stanciu Andreea As932 Data 26 februarie 2020 20:57:47
Problema Grendizer Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 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;
}