Cod sursa(job #67343)

Utilizator info_arrandrei gigea info_arr Data 24 iunie 2007 12:37:57
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
using namespace std;

#define MAX_N 50005

#include <stdio.h>
#include <fstream>

FILE *fin=fopen("pachete.in","r"),
     *fout=fopen("pachete.out","w");

typedef struct 
 {
   int x;
   int y;
 } point;  
     
int s[MAX_N];
point p[MAX_N];
int n,m;

void read (void)
{
  int i,x0,y0;
  fscanf(fin,"%d",&n);
  fscanf(fin,"%d %d",&x0,&y0);
  for (i=1; i<=n ;i++){ 
     fscanf(fin,"%d %d",&p[i].x,&p[i].y);
     p[i].x-=x0; p[i].y-=y0;
   }
}

void part(int st,int dr,int &stst,int &stdr,int &drst,int &drdr)
{
   point aux;
   int i,j,piv;
   piv=p[(st+dr)/2].x; i=st-1; j=dr+1;       
   while (i<j)
    { do {i++;} while (piv>p[i].x); do {j--;} while (piv<p[j].x);
      if (i<j) { aux=p[i]; p[i]=p[j]; p[j]=aux; } }
   if (i==j) { stdr=j-1; drst=i+1; }
    else  { stdr=j; drst=i; }
   stst=st; drdr=dr; 
}

void sort(int st, int dr)
{ int stst,stdr,drst,drdr;
  if (st<dr) { part(st,dr,stst,stdr,drst,drdr);
     sort(stst,stdr); sort(drst,drdr); }
}           

int find (int x)
{
  int mj,li,lf;
  li=1; lf=m;
  if (x<s[m]) {m++; return m; };
  while (li<=lf)
   {
     mj=(li+lf)/2;
     if (s[mj]<x) lf=mj-1;
     if (s[mj]>x) li=mj+1;
     if (s[mj]==x) break;
   }
  return mj;
}      

void solve()
{
  int i,j;
  sort(1,n);
  for (i=1; i<=n; i++)
   {
     j=find(p[i].y); m=j;
     s[j]=p[i].y;
   }
  fprintf(fout,"%d\n",m);       
}  

int main()
{
    read();
    solve();
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}