Cod sursa(job #282786)

Utilizator firewizardLucian Dobre firewizard Data 18 martie 2009 11:17:58
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <stdio.h>  
#include <vector.h>  
#include <algorithm>  
char c,d;  
int n,m,i,j,l,x,y,nr,k,nrc;  
int cx[100005],cy[100005];  
int indx[100005],indy[100005];  
void sud(int);  
void nord(int);  
void vest(int);  
void est(int);  
void bifa(int x,int y)  
{  
 if (x||y)cx[++l]=x;cy[l]=y;//center  
 if (x+1||y+1)cx[++l]=x+1;cy[l]=y+1;//dreapta sus  
 if (x+1||y)cx[++l]=x+1;cy[l]=y;//dreapta 1  
 if (x+1||y-1)cx[++l]=x+1;cy[l]=y-1;//dreapta jos  
 if (x+2||y)cx[++l]=x+2;cy[l]=y;//dreapta 2  
 if (x||y-1)cx[++l]=x;cy[l]=y-1;//jos 1  
 if (x||y-2)cx[++l]=x;cy[l]=y-2;//jos 2  
 if (x||y+1)cx[++l]=x;cy[l]=y+1;//sus 1  
 if (x||y+2)cx[++l]=x;cy[l]=y+2;//sus 2  
 if (x-1||y)cx[++l]=x-1;cy[l]=y;//stanga 1  
 if (x-1||y-1)cx[++l]=x-1;cy[l]=y-1;//stanga jos  
 if (x-1||y+1)cx[++l]=x-1;cy[l]=y+1;//stanga sus  
 if (x-2||y)cx[++l]=x-2;cy[l]=y;//stanga 2  
}  
int bsx(int x,int li,int ls)  
{  
    if(li==ls)return li;  
    int m;  
    m=(li+ls)/2;  
    if (cx[indx[m]]==x)return m;  
    else if (cx[indx[m]]<x)return bsx(x,m+1,ls);  
         else return bsx(x,li,m);  
}  
int bsy(int x,int li,int ls)  
{  
    if(li==ls)return li;  
    int i,m;  
    m=(li+ls)/2;  
    if (cy[indy[m]]==x)return m;  
    else if (cy[indy[m]]<x)return bsy(x,m+1,ls);  
         else return bsy(x,li,m);  
}  
int compx(const void *n1,const void *n2)  
{  
    return cx[*(int *)n1]-cx[*(int *)n2];  
}  
int compy(const void *n1,const void *n2)  
{  
    return cy[*(int *)n1]-cy[*(int *)n2];  
}  
int main()  
{  
    freopen ("zc.in","r",stdin);  
    freopen ("zc.out","w",stdout);  
      
//----------citire--marcaj---------//  
    scanf ("%d %d",&n,&m);  
    for (i=1;i<=n;++i){  
        scanf ("%d %d\n",&x,&y);  
        bifa(x,y);  
        }  
//----------citire--marcaj---------//  
  
//--------preg sort+sort ----------//  
    for (i=1;i<=l;++i){  
        indx[i]=i;  
        indy[i]=i;  
        }  
    qsort(indx+1,l,sizeof(int),compx);  
    qsort(indy+1,l,sizeof(int),compy);  
//--------preg sort+sort ----------//  
  
    i=0;j=0;  
  
//--------------traseu--------------//  
    for (;m;--m){  
        scanf ("%c %d\n",&c,&nr);  
        if (c=='E')est(nr);  
        if (c=='V')vest(nr);  
        if (c=='N')nord(nr);  
        if (c=='S')sud(nr);  
        }  
//--------------traseu---------------//  
  
//-----------afisaje-----------------//  
    printf ("%d\n",nrc);  
//-----------afisaje-----------------//  
    return 0;  
}  
void sud (int x)  
{  
    int li,ls;  
    li=bsy(j-1,1,l);if (cy[indy[li]]!=j-1)li--;  
    ls=bsy(j-x,1,l);  
    for (k=ls;k<=li;++k)  
        if(cx[indy[k]]==i)nrc++;  
    j-=x;  
}  
void nord (int x)  
{  
    int li,ls;  
    li=bsy(j+1,1,l);  
    ls=bsy(j+x,1,l);if (cy[indy[li]]!=j+x)ls--;  
    for (k=li;k<=ls;++k)  
        if(cx[indy[k]]==i)nrc++;  
    j+=x;  
}  
void vest (int x)  
{  
     int li,ls;  
     li=bsx(i-1,1,l);if (cx[indx[li]]!=i-1)li--;  
     ls=bsx(i-x,1,l);  
     for (k=ls;k<=li;++k)  
        if(cy[indx[k]]==j)nrc++;  
    i-=x;  
}  
void est (int x)  
{  
     int li,ls;  
     li=bsx(i+1,1,l);  
     ls=bsx(i+x,1,l);if (cx[indx[li]]!=i+x)ls--;  
     for (k=li;k<=ls;++k)  
        if(cy[indx[k]]==j)nrc++;  
    i+=x;  
}