Cod sursa(job #67428)

Utilizator info_arrandrei gigea info_arr Data 24 iunie 2007 17:11:50
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 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[6][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 cad, int x)
{
  int mj=0,li,lf;
  li=1; lf=s[cad][0];
  if (s[cad][0]==0) { s[cad][0]++; return 1; }
  if (x<s[cad][s[cad][0]]) {s[cad][0]++; return s[cad][0]; };
  while (li<=lf)
   {
     mj=(li+lf)/2;
     if (s[cad][mj]<x) lf=mj-1;
     if (s[cad][mj]>x) li=mj+1;
     if (s[cad][mj]==x) break;
   }
  if (mj>s[cad][0]) s[cad][0]=mj; 
  return mj;
}      

void solve()
{
  int i,j;
  sort(1,n);
  for (i=1; i<=n; i++)
   {
     if (p[i].x<=0 && p[i].y<=0) 
      {j=find(1,abs(p[i].y)); s[1][j]=abs(p[i].y); }
     if (p[i].x<=0 && p[i].y>=0) 
      {j=find(2,p[i].y); s[2][j]=p[i].y; }
     if (p[i].x>=0 && p[i].y>=0) 
      {j=find(3,p[i].y); s[3][j]=p[i].y; }
     if (p[i].x>=0 && p[i].y<=0) 
      {j=find(4,abs(p[i].y)); s[4][j]=abs(p[i].y); }
   }
  m=s[1][0]+s[2][0]+s[3][0]+s[4][0]; 
  fprintf(fout,"%d\n",m);       
}  

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