Cod sursa(job #420468)
Utilizator | Data | 19 martie 2010 12:37:31 | |
---|---|---|---|
Problema | Zota & Chidil | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 4.2 kb |
#include<stdio.h>
#include<algorithm>
using namespace std;
struct bum
{
int x,y;
};
bum a1[100005],b1[100005];
int n,m,u,p1,p2,ps,st,dr,bombe;
int cp1,cp2,me,sc;
void adau(int a,int b)
{
a1[++u].x=a;
a1[u].y=b;
b1[u].x=b;
b1[u].y=a;
}
int cmp(bum a,bum b)
{
if(a.x==b.x)
return (a.y<b.y);
return(a.x<b.x);
}
int main ()
{
int cb,a,b,mut,i,nr1,nr2;
char tip;
freopen("zc.in","r",stdin);
freopen("zc.out","w",stdout);
scanf("%d%d",&n,&me);
for(i=1;i<=n;i++)
{
scanf("%d%d\n",&b,&a);
adau(a-2,b); adau(a+2,b);
adau(a-1,b); adau(a-1,b-1);
adau(a,b); adau(a-1,b+1);
adau(a+1,b); adau(a+1,b-1);
adau(a+1,b+1); adau(a,b-2);
adau(a,b+2); adau(a,b+1); adau(a,b-1);
}
sort(a1+1,a1+u+1,cmp); // dupa coloane
sort(b1+1,b1+u+1,cmp); // dupa linie
nr1=1;nr2=1;
for(i=2;i<=u;i++)
{
if((a1[i].x != a1[i-1].x) || (a1[i].y != a1[i-1].y))
{
a1[++nr1].x=a1[i].x;
a1[nr1].y=a1[i].y;
}
if((b1[i].x != b1[i-1].x) || (b1[i].y != b1[i-1].y))
{
b1[++nr2].x=b1[i].x;
b1[nr1].y=b1[i].y;
}
}
u=nr1;
p1=0;p2=0;
for(i=1;i<=me;i++)
{
scanf("%c%d\n",&tip,&mut);
if(tip=='N')
{
ps=p1+mut;
cb=1;
sc=1;
}
if(tip=='S')
{
ps=p1-mut;
cb=1;
sc=1;mut*=-1;
}
if(tip=='E')
{
ps=p2+mut;
cb=0;sc=2;
}
if(tip=='V')
{
ps=p2-mut;
cb=0;sc=2;mut*=-1;
}
//////////////////////
if(cb==1)
{
st=1;dr=u;
while(st<=dr)
{
m=(st+dr)/2;
if(b1[m].x<p2)
st=m+1;
else
if(b1[m].x>p2)
dr=m-1;
else
{
if(b1[m].y<p1 && b1[m].y<ps)
st=m+1;
else
dr=m-1;
}
}//while
cp1=st;
st=1;dr=u;
while(st<=dr)
{
m=(st+dr)/2;
if(b1[m].x<p2)
st=m+1;
else
if(b1[m].x>p2)
dr=m-1;
else
{
if(b1[m].y>p1 && b1[m].y>ps)
dr=m-1;
else
st=m+1;
}
}//while
cp2=dr;
if(cp2 && cp1)
bombe+=cp2-cp1+1;
}// if
else
{
st=1;dr=u;
while(st<=dr)
{
m=(st+dr)/2;
if(a1[m].x<p1)
st=m+1;
else
if(a1[m].x>p2)
dr=m-1;
else
{
if(a1[m].y<p2 && a1[m].y<ps)
st=m+1;
else
dr=m-1;
}
}//while
cp1=st;
st=1;dr=u;
while(st<=dr)
{
m=(st+dr)/2;
if(a1[m].x<p1)
st=m+1;
else
if(a1[m].x>p1)
dr=m-1;
else
{
if(a1[m].y>p2 && a1[m].y>ps)
dr=m-1;
else
st=m+1;
}
}//while
cp2=dr;
if(cp2 && cp1 && cp2>=cp1)
bombe+=cp2-cp1+1;
}
if(sc==1)
p1+=mut;
else
p2+=mut;
} //for
printf("%d\n",bombe);
return 0;
}