Cod sursa(job #2138652)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 21 februarie 2018 20:06:08
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <vector>
#include <fstream>
#include <deque>
#include <algorithm>
#define f first
#define s second

using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
deque<int> a;
vector<pair<int, int> > v1, v2, v3, v4;
int i,x,y,aa,bb,n;


void cadran(int a,int b)
{
    if(a>=0&&b>=0)
    {
        v1.push_back(make_pair(a, b));
        return;
    }
    if(a<=0&&b>=0)
    {
        v2.push_back(make_pair(-a, b));
        return;
    }
    if(a<=0&&b<=0)
    {
        v3.push_back(make_pair(-a, -b));
        return;
    }
    if(a>=0&&b<=0)
    {
        v4.push_back(make_pair(a, -b));
        return;
    }
}

int solve(vector <pair<int, int> > v)
{
    if(v.size()==0)
        return 0;
    sort(v.begin(),v.end());
    a.clear();
    a.push_back(v[0].second);
    for(int i=1;i<v.size();i++){
        if(v[i].second<a[0])
            a.push_front(v[i].second);
        else
        {
            int st, dr;
            st=0;
            dr=a.size()-1;
            while(st<=dr)
            {
                int mid=(st+dr)/2;
                if(a[mid]<=v[i].second)
                    st=mid+1;
                else
                    dr=mid-1;
            }
            a[dr]=v[i].second;
        }
    }
    return a.size();
}

int main()
{
    fin>>n;
    fin>>x>>y;
    for(i=1;i<=n;i++){
        fin>>aa>>bb;
        aa-=x;
        bb-=y;
        cadran(aa, bb);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());
    sort(v4.begin(), v4.end());
    fout<<solve(v1)+solve(v2)+solve(v3)+solve(v4);
    fin.close();
    fout.close();
    return 0;
}