Cod sursa(job #614918)

Utilizator vlad2901Vlad Berindei vlad2901 Data 7 octombrie 2011 23:58:34
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100000

using namespace std;

struct point
{
    int x, y;
} v1[NMAX], v2[NMAX];

int n, m;

bool cmp1(point a, point b) //sortez dupa x+y
{
    if(a.x + a.y == b.x + b.y)
    {
        return a.x < b.x;
    }
    return a.x + a.y < b.x + b.y;
}

bool cmp2(point a, point b)
{
    if(a.x - a.y == b.x - b.y)
    {
        return a.x < b.x;
    }
    return a.x - a.y < b.x - b.y;
}

int binary_search1(int s, int x)
{
    int st, dr, m, sol;

    st = 0;
    dr = n-1;
    sol = -1;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v1[m].x + v1[m].y < s || (v1[m].x + v1[m].y == s && v1[m].x <= x))
        {
            sol = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return sol;
}

int binary_search2(int d, int x)
{
    int st, dr, m, sol;

    st = 0;
    dr = n-1;
    sol = -1;

    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v2[m].x - v2[m].y < d ||(v2[m].x - v2[m].y == d && v2[m].x <= x))
        {
            sol = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }
    return sol;

}

int main()
{
    int i, x, y, r, dist;

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

    scanf("%d %d", &n, &m);

    for(i=0;i<n;++i)
    {
        scanf("%d %d", &v1[i].x, &v1[i].y);
        v2[i] = v1[i];
    }

    sort(v1, v1+n, cmp1); //sortez dupa x + y
    sort(v2, v2+n, cmp2); //sortez dupa x - y

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

        dist = 0;

        dist += binary_search1(x+y-r, x) - binary_search1(x+y-r ,x-r-1);
        dist += binary_search1(x+y+r, x+r) - binary_search1(x+y+r ,x-1);
        dist += binary_search2(x-y-r, x-1) - binary_search2(x-y-r ,x-r);
        dist += binary_search2(x-y+r, x+r-1) - binary_search2(x-y+r, x);

        printf("%d\n", dist);


    }

    return 0;
}