Cod sursa(job #882159)

Utilizator maritimCristian Lambru maritim Data 18 februarie 2013 22:06:37
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

FILE *f = fopen("zc.in","r");
FILE *g = fopen("zc.out","w");

typedef vector<pair<int,int> >::iterator it;

#define MaxN 1001000
#define MaxTraps (13*MaxN)
#define MH 666013
#define mp make_pair
#define mij ((li+ls)>>1)
#define ll long long

int N,M;
ll Sol;
vector<pair<int,int> > Hash[MH];
vector<pair<int,int> > A,B;

inline int abs(int a)
{
    return a < 0 ? -a : a;
}

inline void addHash(int a,int b)
{
    int x = abs(a)%MH, y = abs(b)%MH;
    x = (x * 100 + y) % MH;

    for(it i=Hash[x].begin();i<Hash[x].end();i++)
        if(i->first == a && i->second == b)
            return ;

    Hash[x].push_back(make_pair(a,b));
}

inline void addTraps(int a,int b)
{
    for(int i=-2;i<=2;i++)
        addHash(a,b+i);

    for(int i=-1;i<=1;i++)
        addHash(a-1,b+i),
        addHash(a+1,b+i);

    addHash(a-2,b);
    addHash(a+2,b);
}

void citire(void)
{
    int a,b;

    fscanf(f,"%d %d\n",&N,&M);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%d %d\n",&b,&a);
        addTraps(a,b);
    }
}

void creareTraps(void)
{
    for(int i=0;i<MH;i++)
        for(it j=Hash[i].begin();j<Hash[i].end();j++)
            if(j->first || j->second)
            A.push_back(mp(j->first,j->second)),
            B.push_back(mp(j->second,j->first));
}

inline int cautBinx(int li,int ls,int a,int k)
{
    if(li > ls)
        return li;

    int x = (k == 0) ? B[mij].first : A[mij].first;

    if(x >= a)
        return cautBinx(li,mij-1,a,k);
    return cautBinx(mij+1,ls,a,k);
}

inline int cautBiny(int li,int ls,int a,int k)
{
    if(li > ls)
        return li;

    int x = (k == 0) ? B[mij].second : A[mij].second;

    if(x >= a)
        return cautBiny(li,mij-1,a,k);
    return cautBiny(mij+1,ls,a,k);
}

void Rezolvare(void)
{
    char op;
    int x,y,a,b,x1,x2,y1,y2,dx,dy;

    x = y = 0;

    creareTraps();

    sort(A.begin(),A.end());
    sort(B.begin(),B.end());

    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%c %d\n",&op,&b);
        a = (op == 'E' || op == 'V');

        switch(op)
        {
            case 'N' : dx = b, dy = 0;
                break;
            case 'E' : dy = b, dx = 0;
                break;
            case 'S' : dx = -b, dy = 0;
                break;
            default : dy = -b, dx = 0;
        }

        if(a)
        {
            x1 = cautBinx(0,A.size()-1,x,a);
            x2 = cautBinx(0,A.size()-1,x+1,a);

            y1 = cautBiny(x1,x2-1,y,a);
            y2 = cautBiny(x1,x2-1,y+dy,a);

            //printf("%d ... %d %d /// y=%d y+dy=%d... %d %d -> ",x,x1,x2,y,y+dy,y1,y2);

        }
        else
        {
            x1 = cautBinx(0,A.size()-1,y,a);
            x2 = cautBinx(0,A.size()-1,y+1,a);

            y1 = cautBiny(x1,x2-1,x,a);
            y2 = cautBiny(x1,x2-1,x+dx,a);

            //printf("%d ... %d %d /// x=%d x+dx=%d %d %d -> ",y,x1,x2,x,x+dx,y1,y2);
        }

        //printf("%d %d ..... %d %d\n",x,y,x+dx,y+dy);

        x += dx;
        y += dy;

        Sol += abs(y2-y1);
    }
    
    //for(int i=0;i<A.size();i++)
    //    printf("%d %d\n",A[i].first,A[i].second);

    //for(int i=0;i<A.size();i++)
    //    printf("%d %d\n",B[i].first,B[i].second);
}

int main()
{
    citire();
    Rezolvare();

    fprintf(g,"%lld\n",Sol);
}