Cod sursa(job #1948888)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 1 aprilie 2017 15:22:53
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#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,1,-1,-1};
int dj[4]={1,-1,1,-1};
FILE *fin,*fout;
int cmp(pct a,pct b){
  if(a.x!=b.x)
    return a.x<b.x;
  return a.y<b.y;
}
int main(){
  fin=fopen("pachete.in","r");
  fout=fopen("pachete.out","w");
  fscanf(fin,"%d%d%d",&n,&a,&b);
  for(i=1;i<=n;i++){
    fscanf(fin,"%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(fout,"%d",s);
  fclose(fin);
  fclose(fout);
  return 0;
}