Cod sursa(job #1560308)

Utilizator ASTELOTudor Enescu ASTELO Data 2 ianuarie 2016 14:45:39
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.83 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct eu{int x,y;};
eu v[100001];
struct eu2{int x1,y1,x2,y2,dir;};
eu2 vc[100001],vcc[1000001];
int xc,yc,i,j,n,m,dir,cate;
char c;
bool sorting(eu2 a,eu2 b)
    {
    if(a.dir<b.dir)
        return 1;
    if(a.dir>b.dir)
        return 0;
    if(a.dir==1&&(a.y1<b.y1||a.y1==b.y1&&a.x1<b.x1))
        return 1;
    if(a.dir==1||(a.x1>b.x1||a.x1==b.x1&&a.y1>b.y1))
        return 0;
    return 1;
    }
int main ()
{
freopen("zc.in","r",stdin);
freopen("zc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
    {
    scanf("%d%d",&v[i].x,&v[i].y);
    cate++;
    vcc[cate].dir=0;
    vcc[cate].x1=v[i].x-2;
    vcc[cate].x2=v[i].x-2;
    vcc[cate].y1=v[i].y;
    vcc[cate].y2=v[i].y;
    cate++;
    vcc[cate].dir=0;
    vcc[cate].x1=v[i].x+2;
    vcc[cate].x2=v[i].x+2;
    vcc[cate].y1=v[i].y;
    vcc[cate].y2=v[i].y;
    cate++;
    vcc[cate].dir=0;
    vcc[cate].x1=v[i].x-1;
    vcc[cate].x2=v[i].x-1;
    vcc[cate].y1=v[i].y-1;
    vcc[cate].y2=v[i].y+1;
    cate++;
    vcc[cate].dir=0;
    vcc[cate].x1=v[i].x+1;
    vcc[cate].x2=v[i].x+1;
    vcc[cate].y1=v[i].y-1;
    vcc[cate].y2=v[i].y+1;
    cate++;
    vcc[cate].dir=0;
    vcc[cate].x1=v[i].x;
    vcc[cate].x2=v[i].x;
    vcc[cate].y1=v[i].y-2;
    vcc[cate].y2=v[i].y+2;
    cate++;
    vcc[cate].dir=1;
    vcc[cate].x1=v[i].x;
    vcc[cate].x2=v[i].x;
    vcc[cate].y1=v[i].y+2;
    vcc[cate].y2=v[i].y+2;
    cate++;
    vcc[cate].dir=1;
    vcc[cate].x1=v[i].x;
    vcc[cate].x2=v[i].x;
    vcc[cate].y1=v[i].y-2;
    vcc[cate].y2=v[i].y-2;
    cate++;
    vcc[cate].dir=1;
    vcc[cate].x1=v[i].x-1;
    vcc[cate].x2=v[i].x+1;
    vcc[cate].y1=v[i].y-1;
    vcc[cate].y2=v[i].y-1;
    cate++;
    vcc[cate].dir=1;
    vcc[cate].x1=v[i].x-1;
    vcc[cate].x2=v[i].x+1;
    vcc[cate].y1=v[i].y+1;
    vcc[cate].y2=v[i].y+1;
    cate++;
    vcc[cate].dir=1;
    vcc[cate].x1=v[i].x-2;
    vcc[cate].x2=v[i].x+2;
    vcc[cate].y1=v[i].y;
    vcc[cate].y2=v[i].y;
    }
for(i=1;i<=m;i++)
    {
    scanf("\n%c%d",&c,&dir);
    if(c=='N')
        {
        vc[i].x1=xc;
        vc[i].y1=yc+1;
        vc[i].x2=xc;
        vc[i].y2=yc+dir;
        yc+=dir;
        vc[i].dir=0;
        }
    if(c=='E')
        {
        vc[i].x1=xc+1;
        vc[i].y1=yc;
        vc[i].x2=xc+dir;
        vc[i].y2=yc;
        xc+=dir;
        vc[i].dir=1;
        }
    if(c=='S')
        {
        vc[i].x1=xc;
        vc[i].y1=yc-dir;
        vc[i].x2=xc;
        vc[i].y2=yc-1;
        yc-=dir;
        vc[i].dir=0;
        }
    if(c=='V')
        {
        vc[i].x1=xc-dir;
        vc[i].y1=yc;
        vc[i].x2=xc-1;
        vc[i].y2=yc;
        xc-=dir;
        vc[i].dir=1;
        }
    }
sort(vc+1,vc+m+1,sorting);
sort(vcc+1,vcc+cate+1,sorting);
int sum=0;
for(i=1;i<=m;i++)
    {
    int l1,l2,mid,nr=0;
    if(vc[i].dir==0)
        {
        l1=1;
        l2=cate/2;
        int o=0;
        while(l1<=l2)
            {
            mid=(l1+l2)/2;
            if(vcc[mid].x1==vc[i].x1)
                {
                o=mid;
                l2=mid-1;
                }
            else
                if(vcc[mid].x1>=vc[i].x1)
                    l2=mid-1;
                else
                    l1=mid+1;
            }
        if(o!=0)
            {
            eu inter;
            mid=o;
            inter.x=-2000000001;
            inter.y=-2000000002;
            while(vcc[mid].x1==vc[i].x1)
                {
                if(vcc[mid].y1>=inter.y)
                    {
                    if(inter.x<=vc[i].y1)
                        inter.x=vc[i].y1;
                    if(inter.y>=vc[i].y2)
                        inter.y=vc[i].y2;
                    if(inter.y>=inter.x)
                        nr+=inter.y-inter.x+1;
                    inter.x=vcc[mid].y1;
                    inter.y=vcc[mid].y2;
                    }
                else
                    if(vcc[mid].y2>=inter.y)
                        inter.y=vcc[mid].y1;
                mid++;
                }
            if(inter.x<=vc[i].y1)
                inter.x=vc[i].y1;
            if(inter.y>=vc[i].y2)
                inter.y=vc[i].y2;
            if(inter.y>=inter.x)
                nr+=inter.y-inter.x+1;
            }
        }
    else
        {
        l1=cate/2+1;
        l2=cate;
        int o=0;
        while(l1<=l2)
            {
            mid=(l1+l2)/2;
            if(vcc[mid].y1==vc[i].y1)
                {
                o=mid;
                l2=mid-1;
                }
            else
                if(vcc[mid].y1>=vc[i].y1)
                    l2=mid-1;
                else
                    l1=mid+1;
            }
        if(o!=0)
            {
            eu inter;
            mid=o;
            inter.x=-2000000001;
            inter.y=-2000000002;
            while(vcc[mid].y1==vc[i].y1)
                {
                if(vcc[mid].x1>=inter.y)
                    {
                    if(inter.x<=vc[i].x1)
                        inter.x=vc[i].x1;
                    if(inter.y>=vc[i].x2)
                        inter.y=vc[i].x2;
                    if(inter.y>=inter.x)
                        nr+=inter.y-inter.x+1;
                    inter.x=vcc[mid].x1;
                    inter.y=vcc[mid].x2;
                    }
                else
                    if(vcc[mid].x2>=inter.y)
                        inter.y=vcc[mid].x1;
                mid++;
                }
            if(inter.x<=vc[i].x1)
                inter.x=vc[i].x1;
            if(inter.y>=vc[i].x2)
                inter.y=vc[i].x2;
            if(inter.y>=inter.x)
                nr+=inter.y-inter.x+1;
            }
        }
    sum+=nr;
    }
printf("%d",sum);
return 0;
}