Cod sursa(job #1736600)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 2 august 2016 11:33:11
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <algorithm>
#define nmax 50005
using namespace std;
struct point {long long x;long long y;};
point p,v[nmax];
point k[4][nmax];
int n,m,t[4];
long long s[nmax];


bool sortcmp(const point &a,const point &b)
{
    return a.x<b.x;
}
int solve(point q[],int l)
{
    int i,j,o;
    sort(q+1,q+l+1,sortcmp);
    m=0;
    for (i=1;i<=l;i++) {
        j=0;
         for (o=1<<15;o;o>>=1)
            if (j+o<=m&&s[j+o]>q[i].y)
                j+=o;
        j++;
        if (j>m)
            s[++m]=q[i].y;
        else
            s[j]=q[i].y;
    }
    return m;
}
int main()
{
    int i;
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    scanf("%d",&n);
    scanf("%lld %lld",&p.x,&p.y);
    for (i=1;i<=n;i++) {
        scanf("%lld %lld",&v[i].x,&v[i].y);
        v[i].x-=p.x;
        v[i].y-=p.y;
        if (v[i].x>=0&&v[i].y>=0)
            k[0][++t[0]]=v[i];

        if (v[i].x<0&&v[i].y>=0) {
            v[i].x=-v[i].x;
            k[1][++t[1]]=v[i];
        }
        if (v[i].x>=0&&v[i].y<0) {
            v[i].y=-v[i].y;
            k[2][++t[2]]=v[i];
        }
        if (v[i].x<0&&v[i].y<0) {
            v[i].x=-v[i].x;
            v[i].y=-v[i].y;
            k[3][++t[3]]=v[i];
        }
    }
    printf("%d\n",solve(k[0],t[0])+solve(k[1],t[1])+solve(k[2],t[2])+solve(k[3],t[3]));

    return 0;
}