Cod sursa(job #2342891)
Utilizator | Data | 13 februarie 2019 15:01:56 | |
---|---|---|---|
Problema | Zota & Chidil | Scor | 10 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 6.41 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zc.in");
ofstream cout ("zc.out");
struct ura{
int x,y;
};
ura vc[1300005];
ura vl[1300005];
bool cmp1(ura a , ura b)
{
if (a.x<b.x)
return true;
else
if (a.x>b.x)
return false;
else
{
if (a.y<b.y)
return true;
return false;
}
}
bool cmp2(ura a , ura b)
{
if (a.y<b.y)
return true;
else
if (a.y>b.y)
return false;
else
{
if (a.x<b.x)
return true;
return false;
}
}
int main()
{
int n,mm,st,dr,x,y,s=0,m,x1,x2,y1,y2,poz1,poz2,cnt=0,i,j,l,c,cnt1=0,cnt2=0,lf,cf,dir;
char car;
cin>>n>>mm;
for (i=1;i<=n;i++)
{
cin>>c>>l;
vc[++cnt].x=l-2;
vc[cnt].y=c;
vc[++cnt].x=l-1;
vc[cnt].y=c-1;
vc[++cnt].x=l-1;
vc[cnt].y=c;
vc[++cnt].x=l-1;
vc[cnt].y=c+1;
vc[++cnt].x=l;
vc[cnt].y=c-2;
vc[++cnt].x=l;
vc[cnt].y=c-1;
vc[++cnt].x=l;
vc[cnt].y=c;
vc[++cnt].x=l;
vc[cnt].y=c+1;
vc[++cnt].x=l;
vc[cnt].y=c+2;
vc[++cnt].x=l+1;
vc[cnt].y=c-1;
vc[++cnt].x=l+1;
vc[cnt].y=c;
vc[++cnt].x=l+1;
vc[cnt].y=c+1;
vc[++cnt].x=l+2;
vc[cnt].y=c;
}
for (i=1;i<=cnt;i++)
{
vl[i].x=vc[i].y;
vl[i].y=vc[i].x;
swap(vc[i].x,vc[i].y);
}
cnt1=cnt2=cnt;
sort (vc+1,vc+cnt1+1,cmp2);
sort (vl+1,vl+cnt2+1,cmp1);
x1=0;
y1=0;
x2=0;
y2=0;
for (i=1;i<=mm;i++)
{
cin>>car>>dir;
poz1=poz2=0;
if (car=='N')
{
y2+=dir;
st=1;
dr=cnt;
poz1=poz2=0;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>x1)
dr=m-1;
else
if (vl[m].x<x1)
st=m+1;
else
{
if (vl[m].y>y1)
{
poz1=m;
dr=m-1;
}
else
st=m+1;
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>x2)
dr=m-1;
else
if (vl[m].x<x2)
st=m+1;
else
{
if (vl[m].y<=y2)
{
poz2=m;
st=m+1;
}
else
dr=m-1;
}
}
}
else
if (car=='S')
{
y2-=dir;
st=1;
dr=cnt;
poz1=poz2=0;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>x2)
dr=m-1;
else
if (vl[m].x<x2)
st=m+1;
else
{
if (vl[m].y>=y2)
{
poz1=m;
dr=m-1;
}
else
st=m+1;
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>x1)
dr=m-1;
else
if (vl[m].x<x1)
st=m+1;
else
{
if (vl[m].y<y1)
{
poz2=m;
st=m+1;
}
else
dr=m-1;
}
}
}
else
if (car=='E')
{
x2+=dir;
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].y>y1)
dr=m-1;
else
if (vc[m].y<y1)
st=m+1;
else
{
if (vc[m].x>x1)
{
poz1=m;
dr=m-1;
}
else
st=m+1;
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if(vc[m].y>y2)
dr=m-1;
else
if (vc[m].y<y2)
st=m+1;
else
{
if (vc[m].x<=x2)
{
poz2=m;
st=m+1;
}
else
dr=m-1;
}
}
}
else
if (car=='V')
{
x2-=dir;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].y>y2)
dr=m-1;
else
if (vc[m].y<y2)
st=m+1;
else
{
if (vc[m].x>=x2)
{
poz1=m;
dr=m-1;
}
else
st=m+1;
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if(vc[m].y>y1)
dr=m-1;
else
if (vc[m].y<y1)
st=m+1;
else
{
if (vc[m].x<x1)
{
poz2=m;
st=m+1;
}
else
dr=m-1;
}
}
}
if (poz1!=0&&poz2!=0)
s=s+(poz2-poz1+1);
x1=x2; y1=y2;
}
cout<<s;
return 0;
}