Cod sursa(job #1523828)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 13 noiembrie 2015 13:12:29
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXC 4
#define MAXN 50000
#define BUF_SIZE 4096
struct mycreation{
    int x, y;
};
mycreation a[MAXN];
int dx[MAXC]={1, 1, -1, -1}, dy[MAXC]={1, -1, 1, -1}, t[MAXN], x[MAXN], y[MAXN];
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fin);
        pos=0;
    }
    return buf[pos++];
}
inline int read(){
    int x=0;
    char ch=nextch();
    while(!isdigit(ch)){
        ch=nextch();
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x;
}
bool cmp(const mycreation a, const mycreation b){
    return a.x<b.x;
}
inline int solve(mycreation v[], int n){
    int i, rez, pas, k;
    std::sort(v, v+n, cmp);
    k=0;
    for(i=0; i<n; i++){
        rez=-1;
        for(pas=1<<15; pas; pas>>=1){
            if((rez+pas<k)&&(t[rez+pas]>=v[i].y)){
                rez+=pas;
            }
        }
        if(rez==-1){
            t[k++]=v[i].y;
        }else{
            t[rez]=v[i].y;
        }
    }
    return k;
}
int main(){
    int ans, n, ox, oy, cadru, i, k;
    FILE *fout;
    fin=fopen("pachete.in", "r");
    fout=fopen("pachete.out", "w");
    n=read();
    ox=read();
    oy=read();
    for(i=0; i<n; i++){
        x[i]=read()-ox;
        y[i]=read()-oy;
    }
    ans=0;
    for(cadru=0; cadru<MAXC; cadru++){
        k=0;
        for(i=0; i<n; i++){
            x[i]*=dx[cadru];
            y[i]*=dy[cadru];
            if((x[i]>0)&&(y[i]>0)){
                a[k].x=x[i];
                a[k].y=y[i];
                k++;
            }
        }
        ans+=solve(a, k);
        for(i=0; i<n; i++){
            x[i]/=dx[cadru];
            y[i]/=dy[cadru];
        }
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}