Cod sursa(job #1247083)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 22 octombrie 2014 01:35:20
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct pct{
    int x;
    int y;
}v[50100],x[50100];
int n,i,j,a,b,d,nr,q,z[50100],p,u,mid,s;
int di[4]={1,0,-1,0};
int dj[4]={0,1,0,-1};
FILE *f,*g;
int cmp(pct a,pct b){
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
int main(){
    f=fopen("pachete.in","r");
    g=fopen("pachete.out","w");
    fscanf(f,"%d%d%d",&n,&a,&b);
    for(i=1;i<=n;i++){
        fscanf(f,"%d%d",&v[i].x,&v[i].y);
        v[i].x-=a;
        v[i].y-=b;
    }
    for(d=0;d<=3;d++){
        nr=0;
        for(i=1;i<=n;i++){
            if(v[i].x*di[d]>=0&&v[i].y*dj[d]>=0){
                x[++nr].x=v[i].x*di[d];
                x[nr].y=v[i].y*dj[d];
            }
        }
        q=0;
        if(nr!=0){
            z[0]=-1;
            z[++q]=1;
        }
        sort(x+1,x+nr+1,cmp);
        for(i=2;i<=nr;i++){
            p=1;
            u=q;
            while(p<=u){
                mid=(p+u)/2;
                if(x[z[mid]].y>x[i].y)
                    p=mid+1;
                else
                    u=mid-1;
            }
            z[p]=i;
            if(p>q)
                q=p;
        }
        s+=q;
    }
    fprintf(g,"%d",s);



    fclose(f);
    fclose(g);
    return 0;
}