Cod sursa(job #2556618)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 25 februarie 2020 08:04:55
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int nr;
deque< pair<int,int> > d[5];
deque<int> bin;
int st,dr,n,i,x,y,X,Y;
void solve(deque<pair<int,int> > d)
{
    sort(d.begin(),d.end());
    bin.clear();
    for(int i=0; i<d.size(); i++)
    {
        int x=d[i].first;
        int y=d[i].second;
        st=0;
        dr=bin.size()-1;
        if(dr<0||bin[dr]>y)
        {
            bin.push_back(y);
        }
        else
        {
            st=0;
            dr=bin.size()-1;
            while(st<=dr)
            {
                int mid=(st+dr)/2;
                if(bin[mid]<=y)
                {
                    dr=mid-1;
                }
                else st=mid+1;
            }
            if(st<=bin.size()-1)
               bin[st]=y;
                else bin.push_back(y);
        }
    }

    nr+=bin.size();
}
int main()
{
    fin>>n;
    fin>>X>>Y;
    for(i=1; i<=n; i++)
    {
        fin>>x>>y;
        x-=X;
        y-=Y;
        if(x>=0&&y>0)
        {
            d[1].push_back({x,y});
        }
        else if(x<0&&y>=0)
        {
            d[2].push_back({-x,y});
        }
        else if(x<=0&&y<0)
        {
            d[3].push_back({-x,-y});
        }
        else d[4].push_back({x,-y});
    }
    for(int i=1; i<=4; i++)
        solve(d[i]);
        fout<<nr;
}