Cod sursa(job #1939052)

Utilizator MarcSpataruMarc Spataru MarcSpataru Data 25 martie 2017 13:38:27
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.03 kb
#include<algorithm>
#include<cstdio>
using namespace std;
struct pachete
{
    int x,y;
};
pachete v[50001];
bool sortare(pachete a,pachete b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int drumurisd[50001],drumurijd[50001],drumurijs[50001],drumuriss[50001];
int main()
{
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    int n,xs,ys,i,nrdrumurisd,nrdrumurijd,nrdrumurijs,nrdrumuriss,l1,l2,mij,f;
    nrdrumurijd=nrdrumurijs=nrdrumurisd=nrdrumuriss=0;
    scanf("%d%d%d",&n,&xs,&ys);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].x,&v[i].y);
    }
    sort(v+1,v+n+1,sortare);
    for(i=1;i<=n;i++)
    {
        if(v[i].x>xs&&v[i].y>ys)//CADRANUL SUS-DREAPTA
        {
            if(nrdrumurisd==0)
            {
                drumurisd[++nrdrumurisd]=v[i].y;
            }
            else
            {
                l1=1;
                l2=nrdrumurisd;
                f=-1;
                while(l1<=l2)
                {
                    mij=(l1+l2)/2;
                    if(drumurisd[mij]>v[i].y)
                    {
                        l1=mij+1;

                    }
                    else
                    {
                        l2=mij-1;
                        f=mij;
                    }
                }

                if(f==-1)
                    drumurisd[++nrdrumurisd]=v[i].y;
                else
                    drumurisd[f]=v[i].y;
            }
        }
        if(v[i].x>xs&&v[i].y<ys)//CADRANUL JOS-DREAPTA
        {
            if(nrdrumurijd==0)
            {
                drumurijd[++nrdrumurijd]=v[i].y;
            }
            else
            {
                l1=1;
                l2=nrdrumurijd;
                f=-1;
                while(l1<=l2)
                {
                    mij=(l1+l2)/2;
                    if(drumurijd[mij]<v[i].y)
                    {
                        l1=mij+1;

                    }
                    else
                    {
                        l2=mij-1;
                        f=mij;
                    }
                }
                if(f==-1)
                    drumurijd[++nrdrumurijd]=v[i].y;
                else
                    drumurijd[f]=v[i].y;
            }
        }
        if(v[i].x<xs&&v[i].y<ys)//CADRANUL JOS-STANGA
        {
            if(nrdrumurijs==0)
            {
                drumurijs[++nrdrumurijs]=v[i].y;
            }
            else
            {
                l1=1;
                l2=nrdrumurijs;
                f=-1;
                while(l1<=l2)
                {
                    mij=(l1+l2)/2;
                    if(drumurijs[mij]<v[i].y)
                    {
                        l1=mij+1;
                        f=mij;
                    }
                    else
                    {
                        l2=mij-1;
                    }
                }

                if(f==-1)
                    drumurijs[++nrdrumurijs]=v[i].y;
                else
                    drumurijs[f]=v[i].y;
            }
        }
        if(v[i].x<xs&&v[i].y>ys)//CADRANUL SUS-STANGA
        {
            if(nrdrumuriss==0)
            {
                drumuriss[++nrdrumuriss]=v[i].y;
            }
            else
            {
                l1=1;
                l2=nrdrumuriss;
                f=-1;
                while(l1<=l2)
                {
                    mij=(l1+l2)/2;
                    if(drumuriss[mij]>v[i].y)
                    {
                        l1=mij+1;
                        f=mij;
                    }
                    else
                    {
                        l2=mij-1;
                    }
                }

                if(f==-1)
                    drumuriss[++nrdrumuriss]=v[i].y;
                else
                    drumuriss[f]=v[i].y;
            }
        }
    }
    printf("%d",nrdrumurisd+nrdrumurijd+nrdrumurijs+nrdrumuriss);
    return 0;
}