Cod sursa(job #1914881)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 martie 2017 18:49:21
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
# include <fstream>
# include <algorithm>
# include <vector>
# define f first
# define s second
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
vector<pair<int,int> > a,b,c,d;
vector<int> s;
int n,x,y,i,X,Y,sol;
int cauta(int val){
    int step,j;
    if(s.size()==0)
        return 0;
    for(step=1;step<=s.size();step*=2);
    for(j=-1;step;step/=2)
        if(step+j<s.size())
            if(s[step+j]>val)
                j+=step;
    return j+1;
}
void cadran(vector<pair<int,int> > a){
    if(a.size()==0)
        return;
    sort(a.begin(),a.end());
    for(i=0;i<a.size();i++)
        if(cauta(a[i].s)==s.size())
            s.push_back(y);
        else
            s[cauta(a[i].s)]=y;
    sol+=s.size();
}
int main () {
    fin>>n>>x>>y;
    for(i=1;i<=n;i++){
        fin>>X>>Y;
        X-=x;
        Y-=y;
        if(X>0&&Y>0)
            a.push_back(make_pair(X,Y));
        if(X<0&&Y>0)
            b.push_back(make_pair(X,Y));
        if(X<0&&Y<0)
            c.push_back(make_pair(X,Y));
        if(X>0&&Y<0)
            d.push_back(make_pair(X,Y));
    }
    cadran(a);
    for(i=0;i<b.size();i++)
        b[i].f*=-1;
    s.clear();
    cadran(b);
    for(i=0;i<c.size();i++){
        c[i].f*=-1;
        c[i].s*=-1;
    }
    s.clear();
    cadran(c);
    for(i=0;i<d.size();i++)
        d[i].s*=-1;
    s.clear();
    cadran(d);
    fout<<sol<<"\n";
    return 0;
}