Cod sursa(job #1679111)

Utilizator akaprosAna Kapros akapros Data 7 aprilie 2016 18:12:50
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.36 kb
#include <bits/stdc++.h>
#define maxN 13 * 100002
#define ll long long
using namespace std;
struct coord
{
    int x, y;
} v[maxN], vx[maxN], vy[maxN], pos;
int n, m, N, a[4002][4002];
ll ans;
/*int cmpx(const coord a, const coord b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
int cmpy(const coord a, const coord b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}
int bsx(int x)
{
    int i = 0, p = 1 << 20;
    while (p)
    {
        if (i + p <= n && vx[i + p].x < x)
            i += p;
        p /= 2;
    }
    return min(n, i + 1);
}
int bsy(int x)
{
    int i = 0, p = 1 << 20;
    while (p)
    {
        if (i + p <= n && vy[i + p].y < x)
            i += p;
        p /= 2;
    }
    return min(n, i + 1);
}
int Bsx(int x, int y)
{
    int i = x, p = 1 << 20;
    while (p)
    {
        if (i + p <= n && vx[i + p].x == vx[x].x && vx[i + p].y < y)
            i += p;
        p /= 2;
    }
    if (vx[i].y < y && i <= n)
        ++ i;
    return i;
}
int Bsy(int x, int y)
{
    int i = x, p = 1 << 20;
    while (p)
    {
        if (i + p <= n && vy[i + p].y == vy[x].y && vy[i + p].x < y)
            i += p;
        p /= 2;
    }
    if (vy[i].x < y)
        ++ i;
    return i;
}*/
void BRUT()
{
    int i, px, py;
    for (i = 1; i <= n; ++ i)
    {
        int cx, cy;
        scanf("%d %d", &cx, &cy);
        cx += 1000; cy += 1000;
        for (px = 0; px <= 2; ++ px)
            for (py = 0; py <= 2; ++ py)
                if (px + py <= 2)
                {
                    a[cx + px][cy + py] = 1;
                    a[cx - px][cy + py] = 1;
                    a[cx + px][cy - py] = 1;
                    a[cx - px][cy - py] = 1;
                }
    }
    coord pos;
    pos.x = pos.y = 1000;
    for (i = 1; i <= m; ++ i)
    {
        int x, j;
        char d;
        scanf("\n%c %d", &d, &x);
        if (d == 'N')
        {
            for (j = pos.y + 1; j <= pos.y + x; ++ j)
                ans += a[pos.x][j];
            pos.y += x;
        }
        if (d == 'S')
        {
            for (j = pos.y - 1; j >= pos.y - x; -- j)
                ans += a[pos.x][j];
            pos.y -= x;
        }
        if (d == 'E')
        {
            for (j = pos.x + 1; j <= pos.x + x; ++ j)
                ans += a[j][pos.y];
            pos.x += x;
        }
        if (d == 'V')
        {
            for (j = pos.x - 1; j >= pos.x - x; -- j)
                ans += a[j][pos.y];
            pos.x -= x;
        }
    }
    //printf("%lld", ans);
}
void read()
{
    int i, px, py;
    freopen("zc.in", "r", stdin);
    scanf("%d %d", &n, &m);
    BRUT();
}
    /*N = 0;
    for (i = 1; i <= n; ++ i)
    {
        int cx, cy;
        scanf("%d %d", &cx, &cy);
        for (px = 0; px <= 2; ++ px)
            for (py = 0; py <= 2; ++ py)
                if (px + py <= 2)
                {
                    v[++ N].x = cx + px;
                    v[N].y = cy + py;
                    if (px)
                    {
                        v[++ N].x = cx - px;
                        v[N].y = cy + py;
                    }
                    if (py)
                    {
                        v[++ N].x = cx + px;
                        v[N].y = cy - py;
                    }
                    if (px && py)
                    {
                        v[++ N].x = cx - px;
                        v[N].y = cy - py;
                    }
                }
    }
}
void det_pos()
{
    int i;
    sort(v + 1, v + N + 1, cmpx);
    n = 0;
    for (i = 1; i <= N; ++ i)
        if (i == 1 || v[i].x != v[i - 1].x || v[i].y != v[i - 1].y)
        {
            vx[++ n] = v[i];
            vy[n] = v[i];
        }
    sort(vx + 1, vx + n + 1, cmpx);
    sort(vy + 1, vy + n + 1, cmpy);
}
void solve()
{
    int p, i;
    det_pos();
    pos.x = pos.y = 0;
    for (i = 1; i <= m; ++ i)
    {
        char d;
        int x, a, b;
        scanf("\n%c %d", &d, &x);
        if (i == 1)
        {-- x;
        if (d == 'N')
            ++ pos.y;
        else
            if (d == 'S')
               -- pos.y;
        else
            if (d == 'E')
               ++ pos.x;
        else
            -- pos.x;}
        if (d == 'N')
        {
            p = bsx(pos.x);
            if (vx[p].x == pos.x)
                {
                    a = Bsx(p, pos.y + x);
                    if (vx[a].x != vx[p].x || vx[a].y > pos.y + x)
                        -- a;
                    b = Bsx(p, pos.y);
                    if (a >= b)
                    ans += 1LL * (a - b + 1);
                }
            pos.y += x;
        }
        if (d == 'S')
        {
            p = bsx(pos.x);
            if (vx[p].x == pos.x)
                {
                    a = Bsx(p, pos.y);
                    if (vx[a].x != vx[p].x || vx[a].y > pos.y)
                        -- a;
                    b = Bsx(p, pos.y - x);
                    if (vx[b].y > pos.y - x || vx[b].x != vx[p].x)
                        -- b;

                    if (a >= b)
                    ans += 1LL * (a - b + 1);
                }
            pos.y -= x;
        }
        if (d == 'E')
        {
            p = bsy(pos.y);
            if (vy[p].y == pos.y)
                {
                    a = Bsx(p, pos.x + x);
                    if (vy[a].y != vy[p].y || vy[a].x > pos.x + x)
                        -- a;
                    b = Bsy(p, pos.x);
                    if (a >= b)
                    ans += 1LL * (a - b + 1);
                }
            pos.x += x;
        }
        if (d == 'V')
        {
            p = bsy(pos.y);
            if (vy[p].y == pos.y)
                {
                    a = Bsy(p, pos.x);
                    if (vy[a].y != vy[p].y || vy[a].x > pos.x)
                        -- a;
                    b = Bsy(p, pos.x - x);
                    if (vy[b].x > pos.x - x || vy[b].y != vy[p].y)
                        -- b;
                   if (a >= b)
                    ans += 1LL * (a - b + 1);
                }
            pos.x -= x;
        }
    }
}*/
void write()
{
    freopen("zc.out", "w", stdout);
    printf("%lld", ans);
}
int main()
{
    read();
    //solve();
    write();
    return 0;
}