Cod sursa(job #1946913)

Utilizator adystar00Bunea Andrei adystar00 Data 30 martie 2017 16:29:42
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include<algorithm>
using namespace std;
struct pct{
    long long x;
    long long y;
};
pct start,p[50010],a[4][50010];
long long st[50010];
bool cmp(const pct &a,const pct &b){
    return a.x<b.x;
}
int vc[4];
int ans (pct v[],int n){
    int i,j,step,m=0;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        j=0;
        for(step=(1<<15);step>0;step/=2)
            if(j+step<=m&&st[j+step]>v[i].y)
                j+=step;
        j++;
        if(j>m){
            m++;
            st[m]=v[i].y;
        }
        else
            st[j]=v[i].y;
    }
    return m;
}
int main(){
    ifstream fin ("pachete.in");
    ofstream fout ("pachete.out");
    int n,i;
    fin>>n>>start.x>>start.y;
    for(i=1;i<=n;i++){
        fin>>p[i].x>>p[i].y;
        p[i].x-=start.x;
        p[i].y-=start.y;
        if(p[i].x>=0&&p[i].y>=0){
            vc[0]++;
            a[0][vc[0]]=p[i];
        }
        if(p[i].x<0&&p[i].y>=0){
            p[i].x*=-1;
            vc[1]++;
            a[1][vc[1]]=p[i];
        }
        if(p[i].x>=0&&p[i].y<0){
            p[i].y*=-1;
            vc[2]++;
            a[2][vc[2]]=p[i];
        }
        if(p[i].x<0&&p[i].y<0){
            p[i].x*=-1;
            p[i].y*=-1;
            vc[3]++;
            a[3][vc[3]]=p[i];
        }
    }
    fout<<ans(a[0],vc[0])+ans(a[1],vc[1])+ans(a[2],vc[2])+ans(a[3],vc[3]);
    return 0;
}