Cod sursa(job #612484)

Utilizator vlad2901Vlad Berindei vlad2901 Data 8 septembrie 2011 00:11:42
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.76 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100000
#define CMAX 2000000000 //cea mai mare coordonata

using namespace std;

struct point
{
    int x, y;
} vx[13*NMAX], vy[13*NMAX], vfx[13*NMAX + 2], vfy[13*NMAX + 2]; //vectori de puncte care vor fi sortati dupa x, respectiv y

int n, m;

int nvx, nvy;

int depx[] = {-2, -1, -1, -1,  0,  0, 0, 0, 0,  1, 1, 1, 2};
int depy[] = { 0, -1,  0,  1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

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

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


//pentru directia N - S
int get_x(int x, int y1, int y2) //cauta punctele afectate de pe coordonata x dintre y1 si y2 inclusiv
{
    int st, dr, m, sol1, sol2;
    st = 0;
    dr = nvx;
    sol1 = 0;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(vfx[m].x < x || (vfx[m].x == x && vfx[m].y < y1))
        {
            sol1 = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }

    sol2 = 0;
    st = 0;
    dr = nvx;

    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(vfx[m].x > x || (vfx[m].x == x && vfx[m].y > y2))
        {
            dr = m - 1;
            sol2 = m;
        }
        else
        {
            st = m + 1;
        }
    }

    if(vfx[sol1+1].x == x && vfx[sol1+1].y >= y1 && vfx[sol2-1].x == x && vfx[sol2-1].y <= y2)
    {
        return sol2 - sol1 - 1;
    }
    return 0;

}

//pentru directia E - V
int get_y(int y, int x1, int x2) //cauta punctele afectate de pe coordonata x dintre y1 si y2 inclusiv
{
    int st, dr, m, sol1, sol2;
    st = 0;
    dr = nvy;
    sol1 = 0;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(vfy[m].y < y || (vfy[m].y == y && vfy[m].x < x1))
        {
            sol1 = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }

    sol2 = 0;
    st = 0;
    dr = nvy;

    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(vfy[m].y > y || (vfy[m].y == y && vfy[m].x > x2))
        {
            dr = m - 1;
            sol2 = m;
        }
        else
        {
            st = m + 1;
        }
    }


    if(vfy[sol1+1].y == y && vfy[sol1+1].x >= x1 && vfy[sol2-1].y == y && vfy[sol2-1].x <= x2)
    {
        return sol2 - sol1 - 1;
    }
    return 0;

}

int main()
{
    int i, j, pas, l, sum, x, y;
    point curent; //punctul curent de pe harta
    char d; //directia

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

    scanf("%d %d", &n, &m);
    pas = 0;

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

        for(j=0;j<13;++j)
        {
            vx[pas].x = vy[pas].x = x + depx[j];
            vx[pas].y = vy[pas].y = y + depy[j];
            ++pas;
        }
    }

    sort(vx, vx+pas, cmpx);
    sort(vy, vy+pas, cmpy);

    //scot dublurile si (0,0)
    vfx[0].x = -CMAX;
    j = 1;


    for(i=0;i<pas;++i)
    {
        while(i < pas && vx[i].x == 0 && vx[i].y == 0)
        {
            ++i;
        }

        vfx[j] = vx[i];
        ++j;

        while(i + 1 < pas && vx[i+1].x == vx[i].x && vx[i+1].y == vx[i].y)
        {
            ++i;
        }

    }

    vfx[j].x = CMAX;
    nvx = j+1;

    vfy[0].y = -CMAX;
    j = 1;

    for(i=0;i<pas;++i)
    {
        vfy[j] = vy[i];
        ++j;

        while(i + 1 < pas && vy[i+1].x == vy[i].x && vy[i+1].y == vy[i+1].x)
        {
            ++i;
        }
    }

    vfy[j].y = CMAX;
    nvy = j+1;

    curent.x = 0;
    curent.y = 0;
    sum = 0;

    for(i=0;i<m-1;++i)
    {
        scanf("\n%c", &d);
        scanf("%d", &l);

        if(d == 'N')
        {
            //caut punctele dintre (curent.x, curent.y) si (curent.x, curent.y + l)
            sum += get_x(curent.x, curent.y, curent.y + l - 1);
            curent.y += l;
            continue;
        }
        if(d == 'S')
        {
            sum += get_x(curent.x, curent.y - l + 1, curent.y);
            curent.y -= l;
            continue;
            //caut punctele dintre (curent.x, curent.y) si (curent.x, curent.y - l)
        }
        if(d == 'E')
        {
            sum += get_y(curent.y, curent.x, curent.x + l - 1);
            curent.x += l;
            continue;
            //caut punctele dintre (curent.x, curent.y) si (curent.x + l, curent.y)
        }
        if(d == 'V')
        {
            //caut punctele dintre (curent.x, curent.y) si (curent.x - l, curent.y)
            sum += get_y(curent.y, curent.x - l + 1, curent.x);
            curent.x -= l;
            continue;
        }
    }

     scanf("\n%c", &d);
        scanf("%d", &l);

        if(d == 'N')
        {
            //caut punctele dintre (curent.x, curent.y) si (curent.x, curent.y + l)
            sum += get_x(curent.x, curent.y, curent.y + l);
            curent.y += l;
        }
        if(d == 'S')
        {
            sum += get_x(curent.x, curent.y - l, curent.y);
            curent.y -= l;
            //caut punctele dintre (curent.x, curent.y) si (curent.x, curent.y - l)
        }
        if(d == 'E')
        {
            sum += get_y(curent.y, curent.x, curent.x + l);
            curent.x += l;
            //caut punctele dintre (curent.x, curent.y) si (curent.x + l, curent.y)
        }
        if(d == 'V')
        {
            //caut punctele dintre (curent.x, curent.y) si (curent.x - l, curent.y)
            sum += get_y(curent.y, curent.x - l, curent.x);
            curent.x -= l;
        }

    printf("%d", sum);


    return 0;
}