Cod sursa(job #3257111)

Utilizator mihaigeorgescuGeorgescu Mihai mihaigeorgescu Data 16 noiembrie 2024 17:58:34
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fcin("pachete.in");
ofstream fout("pachete.out");
int ap[50001],x1,y1,n,vf0,vf1,vf2,vf3,a,b,dp[50001],vf,rez;
struct pct
{
    int x;
    int y;
};
pct v[4][50001];
inline int cb(int val)
{
    int st=1;
    int dr=vf;
     while(st<=dr)
     {
         int mij=(st+dr)/2;
         if(dp[mij]<=val)
            dr=mij-1;
         else
            st=mij+1;
     }
     return st;
}
inline bool f(pct x, pct y)
{
    if(x.x==y.x)
        return x.y<y.y;
    return x.x<y.x;
}
inline int nrsc(int cnt,int sz)
{
    int nr=0;
    vf=1;
    dp[1]=v[cnt][1].y;
    for(int i=2; i<=sz; i++)
    {
        int poz=cb(v[cnt][i].y);
        if(poz>vf)
        {
            vf++;
        }
        dp[poz]=v[cnt][i].y;
    }
    return vf;
}
int main()
{
    fcin>>n;
    fcin>>x1>>y1;
    for(int i=1; i<=n; i++)
    {
        fcin>>a>>b;
        a=a-x1;
        b=b-y1;
        if(a>=0 && b>=0)
        {
            v[0][++vf0]={a,b};
        }
        if(a>=0 && b<=0)
        {
            v[1][++vf1]={a,-b};
        }
        if(a<=0 && b<=0)
        {
            v[2][++vf2]={-a,-b};
        }
        if(a<=0 && b>=0)
        {
            v[3][++vf3]={-a,b};
        }
    }
    if(vf0>0)
    sort(v[0]+1, v[0]+vf0+1, f), rez=rez+nrsc(0,vf0);
    if(vf1>0)
    sort(v[1]+1, v[1]+vf1+1, f), rez=rez+nrsc(1,vf1);
    if(vf2>0)
    sort(v[2]+1, v[2]+vf2+1, f), rez=rez+nrsc(2,vf2);
    if(vf3>0)
    sort(v[3]+1, v[3]+vf3+1, f), rez=rez+nrsc(3,vf3);
    fout<<rez;
    return 0;
}