Cod sursa(job #1807789)

Utilizator silkMarin Dragos silk Data 16 noiembrie 2016 21:59:40
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <cstdio>
#include <algorithm>
#define NMax 100000
using namespace std;

struct pct{ int x,y; };
pct v[NMax+1];
pct u[NMax+1];

int N,ans;

bool cmp1(const pct A, const pct B)
{
    if( A.x+A.y==B.x+B.y ) return A.y<B.y;
    return A.x+A.y < B.x+B.y;
}

bool cmp2(const pct A, const pct B)
{
    if( A.x-A.y==B.x-B.y ) return A.y<B.y;
    return A.x-A.y < B.x-B.y;
}

void princ(int r, int a, int b)
{
    int f1,f2,st,dr,mid;

    for(f1 = -1, st = 1, dr = N; st <= dr; )
    {
        mid = (st+dr)/2;
        if( u[mid].x+u[mid].y < r ) st = mid+1;
        else if( u[mid].x+u[mid].y > r ) dr = mid-1;
        else
        {
            if( u[mid].y < a ) st = mid+1;
            else { f1 = mid; dr = mid-1; }
        }
    }

    for(f2 = -1, st = 1, dr = N; st <= dr; )
    {
        mid = (st+dr)/2;
        if( u[mid].x+u[mid].y < r ) st = mid+1;
        else if( u[mid].x+u[mid].y > r ) dr = mid-1;
        else
        {
            if( u[mid].y > b ) dr = mid-1;
            else { f2 = mid; st = mid+1; }
        }
    }

    if( f1>0 && f2>0 ) ans += f2-f1+1;
}

void sec(int r, int a, int b)
{
    int f1,f2,st,dr,mid;

    for(f1 = -1, st = 1, dr = N; st <= dr; )
    {
        mid = (st+dr)/2;
        if( v[mid].x-v[mid].y < r ) st = mid+1;
        else if( v[mid].x-v[mid].y > r ) dr = mid-1;
        else
        {
            if( v[mid].y < a ) st = mid+1;
            else { f1 = mid; dr = mid-1; }
        }
    }

    for(f2 = -1, st = 1, dr = N; st <= dr; )
    {
        mid = (st+dr)/2;
        if( v[mid].x-v[mid].y < r ) st = mid+1;
        else if( v[mid].x-v[mid].y > r ) dr = mid-1;
        else
        {
            if( v[mid].y > b ) dr = mid-1;
            else { f2 = mid; st = mid+1; }
        }
    }

    if( f1>0 && f2>0 ) ans += f2-f1+1;
}

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

    int i,M,x,y,r;

    scanf("%d %d",&N,&M);
    for(i = 1; i <= N; ++i)
    {
        scanf("%d %d",&x,&y);
        u[i].x = v[i].x = x;
        u[i].y = v[i].y = y;
    }

    sort(u+1,u+N+1,cmp1);
    sort(v+1,v+N+1,cmp2);

    for(i = 1; i <= M; ++i)
    {
        ans = 0;
        scanf("%d %d %d",&x,&y,&r);

        princ(x+y-r,y-r,y);
        princ(x+y+r,y,y+r);
        sec(x-y+r,y-r+1,y-1);
        sec(x-y-r,y+1,y+r-1);

        printf("%d\n",ans);
    }



return 0;
}