Cod sursa(job #2112495)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 23 ianuarie 2018 15:51:08
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<fstream>
#include<string.h>
#include<algorithm>
using namespace std;
ifstream fi("pachete.in");
ofstream fo("pachete.out");
int n,i;
pair<int,int> p,s,C1[50001],C2[50001],C3[50001],C4[50001];
int S[50001],c1,c2,c3,c4,l,rez,poz;

int bs(int st, int dr, int val)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(S[mij]<val && S[mij+1]>=val)
            return mij;
        if(S[mij+1]<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return l;
}

int main()
{
    fi>>n;
    fi>>s.first>>s.second;
    for(i=1; i<=n; i++)
    {
        fi>>p.first>>p.second;
        if(p.first>=s.first && p.second>=s.second)
            C1[++c1]={p.first-s.first,p.second-s.second};
        if(p.first<s.first && p.second>=s.second)
            C2[++c2]={s.first-p.first,p.second-s.second};
        if(p.first>=s.first && p.second<s.second)
            C3[++c3]={p.first-s.first,s.second-p.second};
        if(p.first<s.first && p.second<s.second)
            C4[++c4]={s.first-p.first,s.second-p.second};
    }
    sort(C1+1,C1+c1+1);
    sort(C2+1,C2+c2+1);
    sort(C3+1,C3+c3+1);
    sort(C4+1,C4+c4+1);
    for(i=1; i<=c1; i++)
    {
        poz=bs(0,l,C1[i].second);
        poz++;
        if(poz==l+1)
            l++;
        S[poz]=C1[i].second;
    }
    rez=l;
    l=0;
    memset(S,0,sizeof(S));
    for(i=1; i<=c2; i++)
    {
        poz=bs(0,l,C2[i].second);
        poz++;
        if(poz==l+1)
            l++;
        S[poz]=C2[i].second;
    }
    rez+=l;
    l=0;
    memset(S,0,sizeof(S));
    for(i=1; i<=c3; i++)
    {
        poz=bs(0,l,C3[i].second);
        poz++;
        if(poz==l+1)
            l++;
        S[poz]=C3[i].second;
    }
    rez+=l;
    l=0;
    memset(S,0,sizeof(S));
    for(i=1; i<=c4; i++)
    {
        poz=bs(0,l,C4[i].second);
        poz++;
        if(poz==l+1)
            l++;
        S[poz]=C4[i].second;
    }
    rez+=l;
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}