Cod sursa(job #1948906)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 1 aprilie 2017 16:18:19
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define MAXN 50000
std::pair <int,int> v[MAXN+1];
int val1[MAXN+1],val2[MAXN+1];
bool viz[MAXN+1];
int main(){
    FILE*fi,*fout;
    int i,n,rez,pas,m1,m2,x,y,ans;
    fi=fopen("pachete.in" ,"r");
    fout=fopen("pachete.out" ,"w");
    fscanf(fi,"%d %d %d " ,&n,&x,&y);
    for(i=1;i<=n;i++){
      fscanf(fi,"%d %d " ,&v[i].x,&v[i].y);
      v[i].x-=x;
      v[i].y-=y;
    }
    std::sort(v+1,v+n+1);
    ans=0;
    m1=m2=0;
    for(i=n;i>=1;i--)
     if(v[i].x>=0&&v[i].y>=0){
        rez=0;
        for(pas=1<<16;pas;pas>>=1)
         if(rez+pas<=m1&&v[i].y>val1[rez+pas])
          rez+=pas;
        if(rez==m1)
           val1[++m1]=v[i].y;
        else
           val1[rez+1]=v[i].y;
        viz[i]=1;
     }
     else if(v[i].x>=0&&v[i].y<0){
        v[i].y=-v[i].y;
        rez=0;
        for(pas=1<<16;pas;pas>>=1)
         if(rez+pas<=m2&&v[i].y>val2[rez+pas])
          rez+=pas;
        if(rez==m2)
           val2[++m2]=v[i].y;
        else
           val2[rez+1]=v[i].y;
        viz[i]=1;
     }
    ans+=m1+m2;
    memset(val1,0,sizeof(val1));
    memset(val2,0,sizeof(val2));
    m1=m2=0;
    for(i=1;i<=n;i++)
      if(viz[i]==0)
         if(v[i].x<0&&v[i].y>=0){
            rez=0;
            for(pas=1<<16;pas;pas>>=1)
             if(rez+pas<=m1&&v[i].y>val1[rez+pas])
              rez+=pas;
            if(rez==m1)
               val1[++m1]=v[i].y;
            else
               val1[rez+1]=v[i].y;
         }
         else if(v[i].x<0&&v[i].y<0){
            v[i].y=-v[i].y;
            rez=0;
            for(pas=1<<16;pas;pas>>=1)
             if(rez+pas<=m2&&v[i].y>val2[rez+pas])
              rez+=pas;
            if(rez==m2)
               val2[++m2]=v[i].y;
            else
               val2[rez+1]=v[i].y;
         }
    ans+=m1+m2;
    fprintf(fout,"%d" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}