Cod sursa(job #22919)

Utilizator pocaituDavid si Goliat pocaitu Data 27 februarie 2007 20:29:07
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<fstream.h>
int long cadr[5][2][50000],nr[6],nn[6],kk[5][10000];
int long x1[50000],y1[50000],x[50000],y[50000],nrr,ys[50000];
int long min1=1,max1=-1,max2=-1,min2=1;
/*ofstream gg("test.out");
void afiseaza_vect(int v[100],int n)
{int i;
 for(i=1;i<=n;i++)
  gg<<v[i]<<" ";
 gg<<'\n';
 } */


void citire()
{int long n,i,xs,ys,a,b;
 ifstream f("pachete.in");
 f>>n>>xs>>ys;
 for(i=1;i<=n;i++)
  {f>>a>>b;
   a-=xs;b-=ys;
   if(a==0&&b!=0)
	 {if(b>0)
		kk[1][++nn[1]]=b;
	  else
		kk[2][++nn[2]]=b*(-1);
	  }
   if(b==0&&a!=0)
	{if(a>0)
	   kk[3][++nn[3]]=a;
	 else
	   kk[4][++nn[4]]=a*(-1);
	 }
   if(a>0&&b>0)
	 {cadr[1][0][++nr[1]]=a;
	  cadr[1][1][nr[1]]=b;
	  }
   if(a>0&&b<0)
	 {cadr[4][0][++nr[4]]=a;
	  cadr[4][1][nr[4]]=b*(-1);
	  }
   if(a<0&&b<0)
	 {cadr[3][0][++nr[3]]=a*(-1);
	  cadr[3][1][nr[3]]=b*(-1);
	  }
   if(a<0&&b>0)
	 {cadr[2][0][++nr[2]]=a*(-1);
	  cadr[2][1][nr[2]]=b;
	  }
   }
}


int long cautare(int long y)
{int long i,d,min=y+1;
 for(i=0;i<=nrr;i++)
  if(y-ys[i]<min&&y-ys[i]>=0)
	d=i;
 return d;
 }



void merge_sort(int long l, int long r)
{
	int long m = (l + r) >> 1, i, j, k;
	if (l == r) return;
	merge_sort(l, m);
	merge_sort(m + 1, r);
	for (i=l, j=m+1, k=l; i<=m || j<=r; )
		if (j > r || (i <= m &&(x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j])))) //A[i] < A[j]))
			{//B[k++] = A[i++];
			 y1[k]=y[i];
			 x1[k++]=x[i++];
			 }
		else
			{//B[k++] = A[j++];
			 y1[k]=y[j];
			 x1[k++]=x[j++];
			 }
	for (k = l; k <= r; k++)
	  {x[k]=x1[k];
	   y[k]=y1[k];
	   }
	  //A[k] = B[k];
}



int long rezolva(int long n)
{nrr=0;
 int long i,c;
 if(n)
 merge_sort(1,n);

 //afiseaza_vect(x,n);
 //afiseaza_vect(y,n);
 for(i=1;i<=n;i++)
  {c=cautare(y[i]);
   if(!c)
	 ys[++nrr]=y[i];
   if(c)
	 ys[c]=y[i];
   }

 return nrr;
 }


int main()
{int long i,sol=0,j;
 citire();
 for(i=1;i<=4;i++)
   {for(j=1;j<=nr[i];j++)
	  {x[j]=cadr[i][0][j];
	   y[j]=cadr[i][1][j];
	   }
   sol+=rezolva(nr[i]);
   }
 ofstream g("pachete.out");
 g<<sol+4;
 g.close();
 return 0;
 }