Cod sursa(job #866237)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 27 ianuarie 2013 18:09:39
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<fstream>
#include<algorithm>

using namespace std;

#define MAXCELL 1200000

typedef struct
{
    int x, y;
} cell;

int N, M, i, j, x, y, k, nr_cells, t1, t2, res;
char c;
cell A;
cell v[ MAXCELL ];

inline int cmp(cell A, cell B)
{
    if(A.x > B.x)
        return 0;
    if(A.x == B.x && A.y > B.y)
        return 0;
    return 1;
}

inline int search(cell A)
{
    int st = 1, end = nr_cells, mid;
    cell B;

    while(st <= end)
    {
        mid = (st + end) / 2;
        B = v[mid];

        if(B.x < A.x)
            st = mid + 1;
        else if(B.x > A.x)
            end = mid - 1;
        else
        {
            if(B.y < A.y)
                st = mid + 1;
            else if(B.y > A.y)
                end = mid - 1;
            else return 1;
        }
    }

    return 0;
}

int main()
{
    ifstream f("zc.in");
    ofstream g("zc.out");

    f >> N >> M;
    for(i = 1; i <= N; ++i)
    {
        f >> x >> y;
        for(t1 = -2; t1 <= 2; ++t1)
            for(t2 = -2; t2 <= 2; ++t2)
                if(abs(t1) + abs(t2) <= 2)
                    ++nr_cells, v[nr_cells].x = x + t1, v[nr_cells].y = y + t2;
    }
    sort(v+1, v+nr_cells+1, cmp);
    v[0].x = v[1].x - 1;
    for(i = 1; i <= nr_cells; ++i)
        if(v[i].x != v[i-1].x || v[i].y != v[i-1].y)
            ++k, v[k].x = v[i].x, v[k].y = v[i].y;
    nr_cells = k;
    x = y = 0;
    for(i = 1; i <= M; ++i)
    {
        f >> c >> k;
        switch(c)
        {
            case 'N':
            {
                for(j = 1; j <= k; ++j)
                {
                    ++y, A.x = x, A.y = y;
                    if(x || y)
                        res += search(A);
                }
            } break;
            case 'S':
            {
                for(j = 1; j <= k; ++j)
                {
                    --y, A.x = x, A.y = y;
                    if(x || y)
                        res += search(A);
                }
            } break;
            case 'V':
            {
                for(j = 1; j <= k; ++j)
                {
                    --x, A.x = x, A.y = y;
                    if(x || y)
                        res += search(A);
                }
            } break;
            case 'E':
            {
                for(j = 1; j <= k; ++j)
                {
                    ++x, A.x = x, A.y = y;
                    if(x || y)
                        res += search(A);
                }
            } break;
        }
    }

    g << res << '\n';

    f.close();
    g.close();

    return 0;
}