Cod sursa(job #1741277)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 13 august 2016 15:19:33
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<cstdio>
#include<algorithm>
#define MAXN 50010
using namespace std;
struct Point{
    long long x;
    long long y;
};
Point start,points[MAXN],quarter[4][MAXN];
long long Stack[MAXN];
bool PointCompare(const Point &a,const Point &b){
    return a.x<b.x;
}
int howMany[4];
int Solve(Point v[],int n){
    int i,j,step,m=0;
    sort(v+1,v+n+1,PointCompare);
    for(i=1;i<=n;i++){
        j=0;
        for(step=(1<<15);step>0;step/=2)
            if(j+step<=m&&Stack[j+step]>v[i].y)
                j+=step;
        j++;
        if(j>m){
            m++;
            Stack[m]=v[i].y;
        }
        else
            Stack[j]=v[i].y;
    }
    return m;
}
int main(){
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    int n,i;
    scanf("%d%lld%lld",&n,&start.x,&start.y);
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&points[i].x,&points[i].y);
        points[i].x-=start.x;
        points[i].y-=start.y;
        if(points[i].x>=0&&points[i].y>=0){
            howMany[0]++;
            quarter[0][howMany[0]]=points[i];
        }
        if(points[i].x<0&&points[i].y>=0){
            points[i].x*=-1;
            howMany[1]++;
            quarter[1][howMany[1]]=points[i];
        }
        if(points[i].x>=0&&points[i].y<0){
            points[i].y*=-1;
            howMany[2]++;
            quarter[2][howMany[2]]=points[i];
        }
        if(points[i].x<0&&points[i].y<0){
            points[i].x*=-1;
            points[i].y*=-1;
            howMany[3]++;
            quarter[3][howMany[3]]=points[i];
        }
    }
    printf("%d",Solve(quarter[0],howMany[0])+Solve(quarter[1],howMany[1])+Solve(quarter[2],howMany[2])+Solve(quarter[3],howMany[3]));
    return 0;
}