Cod sursa(job #281218)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 13 martie 2009 21:59:47
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.47 kb
# include <stdio.h>
# include <stdlib.h>

# define INF 2000000001

typedef struct LISTA {long int *begin, *end;};
typedef struct PUNCT {long int x,y;};
typedef struct LISTE_COORD {long int coord, count; long int *begin;};

int compara_punct_x(const void *aa, const void *bb)
{
    PUNCT *a=(PUNCT *)aa;
    PUNCT *b=(PUNCT *)bb;
    if (a->x > b->x) return 1;
    if (a->x < b->x) return -1;
    if (a->y > b->y) return 1;
    return -1;
}

int compara_punct_y(const void *aa, const void *bb)
{
    PUNCT *a=(PUNCT *)aa;
    PUNCT *b=(PUNCT *)bb;
    if (a->y > b->y) return 1;
    if (a->y < b->y) return -1;
    if (a->x > b->x) return 1;
    return -1;
}

const long int vx[]={0,0,1,0,-1};
const long int vy[]={0,1,0,-1,0};

//////////
// VARIABILE GLOBALE
///////

# define MAXN 100000

long int sol=0;
long int n,m,linlen,collen;
LISTE_COORD lin[MAXN+1],col[MAXN+1];
long int *vallin,*valcol;
LISTA list[5];
long int deplasamente_list[]={-2,-1,0,-1,-2};

void citire_mine(FILE *f)
{
     fscanf(f,"%ld%ld",&n,&m);
     PUNCT *mina=(PUNCT *) malloc (sizeof(PUNCT)*(n+1));
     long int i;
     for (i=1;i<=n;i++)
         fscanf(f,"%ld%ld",&mina[i].x,&mina[i].y);
         
     vallin=(long int*) malloc (sizeof(long int)*(n+1));
     qsort(mina+1,n,sizeof(PUNCT),compara_punct_x);
     //ai punctele sortate in ordinea coordonatei x, acum pe fiecare
     //coordonata iti trebuie un vector
     for (i=1;i<=n;i++)
         {
         vallin[i]=mina[i].y;
         if (i==1 || mina[i].x!=mina[i-1].x)
            {
            linlen++;
            lin[linlen].coord=mina[i].x;
            lin[linlen].count=1;
            lin[linlen].begin=vallin+i;
            }
         else
             lin[linlen].count++;
         }
         
     valcol=(long int*) malloc (sizeof(long int)*(n+1));
     qsort(mina+1,n,sizeof(PUNCT),compara_punct_y);
     mina[0].y=-2000000001;
     //ai coordonatele sortatae in ordinea coordonatei y si repetam
     for (i=1;i<=n;i++)
         {
         valcol[i]=mina[i].x;
         if (i==1 || mina[i].y!=mina[i-1].y)
            {
            collen++;
            col[collen].coord=mina[i].y;
            col[collen].count=1;
            col[collen].begin=valcol+i;
            }
         else
             col[collen].count++;
         }
     free(mina);
} 
     
void test_generare()
{
     long int i,j;
     for (i=1;i<=linlen;i++)
         {
         printf("Linia %ld: \n\t",lin[i].coord);
         for (j=1;j<=lin[i].count;j++)
             printf("%ld ",lin[i].begin[j-1]);
         printf("\n");
         }
     getchar();
}

char index_dir(char dir)
{
     if (dir=='N') return 1;
     if (dir=='E') return 2;
     if (dir=='S') return 3;
     return 4;
}

void interschimba(long int &a, long int &b)
{
     long int aux; aux=a;a=b;b=aux;
}

long int search_b(LISTE_COORD *liste, long int li, long int lf, long int key)
{
     if (li>lf) return 0;
     long int m=(li+lf)/2;
     if (liste[m].coord==key) return m;
     if (liste[m].coord>key) return search_b(liste,li,m-1,key);
     return search_b(liste,m+1,lf,key);
}

long int * cauta_pMM(long int *p, long int n, long int key)
{
     long int li=0,lf=n-1,m;
     if (p[0]>=key) return p;
     if (p[n-1]<key) return NULL;
     while (li<=lf)
           {
           m=(li+lf)/2;
           if (m && p[m]>=key && p[m-1]<key) return p+m;
           if (p[m]<key) li=m+1;
           else lf=m-1;
           }
     return NULL;
}

long int * cauta_pmm(long int *p, long int n, long int key)
{
     long int li=0,lf=n-1,m;
     if (p[n-1]<=key) return p+n-1;
     if (p[0]>key) return NULL;
     while (li<=lf)
           {
           m=(li+lf)/2;
           if (m+1<=n-1 && p[m]<=key && p[m+1]>key) return p+m;
           if (p[m]>key) lf=m-1;
           else li=m+1;
           }
     return NULL;
}

void open_list(LISTA &l,long int coord_key,LISTE_COORD *liste,long int listelen, long int li, long int lf)
{
     //trebuie mai intai sa cautam daca exista o lista cu coord_key
     long int index=search_b(liste,1,listelen,coord_key);
     if (index==0)
        {
        l.begin=NULL;
        l.end=NULL;
        }
     else
         {
         //AICI SE POATE OPTIMIZA MASIV PRIN INCA 2 CAUTARI BINARE
         l.begin=cauta_pMM(liste[index].begin,liste[index].count,li);
         l.end=cauta_pmm(liste[index].begin,liste[index].count,lf);
         if (l.begin==NULL || l.end==NULL || l.end-l.begin<0) 
            {
            l.begin=NULL;
            l.end=NULL;
            }
         }
}

void extract_list(long int &depl, long int &c_bomb, long int &listlen)
{
     long int j,min=-1;
     long int depl2[5]={0,1,2,1,0};
     for (j=0;j<=2;j++)
         {
         if (list[j+2].begin && (min==-1 || (*list[j+2].begin)-depl2[j]<(*list[min].begin)-depl2[min]) ) min=j+2;
         if (j>0 && list[2-j].begin && (min==-1 || (*list[2-j].begin)-depl2[2-j]<(*list[min].begin)-depl2[min] ) ) min=2-j;
         }
     //tre' sa scoti din list
     depl=min;
     if (depl>2) depl%=2;
     c_bomb=*list[min].begin;
     if (list[min].begin==list[min].end)
        {
        list[min].begin=NULL;
        listlen--;
        }
     else
        {
        list[min].begin++;
        //printf("%ld==",*list[min].begin);
        }
}

long int found (long int *v, long int val)
{
     long int i,solloc=0,min;
     for (i=0,min=0;i<=4;i++)
         {
         if (v[i]==val) solloc=1;
         if (v[i]<v[min]) min=i;
         }
     if (v[min]<val) v[min]=val;
     return solloc;
}

void print_liste()
{
     printf("///\n/// Print Liste\n///\n");
     long int j,*p;
     for (j=0;j<=4;j++)
         {
         printf("%ld = ",j-2);
         p=list[j].begin;
         while (p && p<=list[j].end)
               {
               printf("%ld ",*p);
               p++;
               }
         printf("\n");
         }
     printf("////\n");
}
     

long int calculeaza_patratele(long int xi, long int yi, long int xf, long int yf)
{
     long int listslen=0,lastmod[5]={-INF,-INF,-INF,-INF,-INF},li,lf,solloc=0,j,depl,c_bomb,c1;
     //terbuie sa cautam listele corecte;
     if (xi==xf)
        {
        c1=xi;
        if (yf<yi) interschimba(yf,yi);
        li=yi;lf=yf;
        //x ramane constant
        for (j=-2;j<=2;j++)
            {
            open_list(list[j+2],xi+j,lin,linlen,yi,yf);
            if (list[j+2].begin!=NULL) listslen++;
            }
        }
     else
         {
         c1=yi;
         if (xf<xi) interschimba(xf,xi);
         li=xi;lf=xf;
         for (j=-2;j<=2;j++)
             {
             open_list(list[j+2],yi+j,col,collen,xi,xf);
             if (list[j+2].begin!=NULL) listslen++;
             }
         }
     //de aici calculam efectiv

     
     //printf("Segment: %ld %ld %ld %ld\n",xi,yi, xf,yf);
     //printf("Nr de liste : %ld\n",listslen);
     while (listslen)
           {
           //incercam sa gasim pozitia din una din liste care are val-depl minima
           extract_list(depl,c_bomb,listslen);
           //     print_liste();
           //asta e coordonata minima, si care ajunge cel mai departe in spate
           //       printf("variatia: %ld coord_bombei: %ld\n",depl,c_bomb);
           //          getchar();
           for (j=c_bomb-depl;j<=c_bomb+depl;j++)
               if (j>=li && j<=lf && (j!=0 || c1 !=0) )
                  {
                  solloc+=1-found(lastmod,j);
                  //printf("->%ld \n",solloc);
                  }
           }
     return solloc;
}

void calculeaza(FILE *f)
{
     long int pas,x=0,y=0,xnou,ynou;unsigned long int d;char dir;
     
     for (pas=1;pas<=m;pas++)                 
         {
         //citim din "f" o directie si o distanta
         fscanf(f," %c %lu ", &dir, &d);
         dir=index_dir(dir);
         x+=vx[dir];
         y+=vy[dir];
         xnou=x+vx[dir]*(d-1);
         ynou=y+vy[dir]*(d-1);
         //printf("%ld %ld -> %ld %ld\n",x,y,xnou,ynou);
         //getchar();
            sol+=calculeaza_patratele(x,y,xnou,ynou);
         //ATENTIE!!!
         //aici, daca segmentul contine [0,0] si e bomba pe el ar trebui scoasa   
         x=xnou;
         y=ynou;
         }
}

int main()
{
    FILE *f=fopen("zc.in","r");
    citire_mine(f);
    
    //test_generare();
    
    calculeaza(f);
    
    fclose(f);
    FILE *g=fopen("zc.out","w");
    fprintf(g,"%ld\n",sol);
    fclose(g);
    return 0;
}