Cod sursa(job #6917)

Utilizator C_OvidiuCotletz Ovidiu C_Ovidiu Data 21 ianuarie 2007 10:50:51
Problema Pachete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.92 kb
#include<fstream.h>
long long B[50003],client[50003][2],i,n,sediu[2],cadr1[50003],cadr2[50003],st,dr,nr;

void merge_sort(long long l, long long r)
{
	long 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 && (client[cadr1[i]][0]*client[cadr1[j]][1] < client[cadr1[j]][0]*client[cadr1[i]][1])))
			B[k++] = cadr1[i++];
		else
			B[k++] = cadr1[j++];
	for (k = l; k <= r; k++) cadr1[k] = B[k];
}

   void merge_sort2(long long l,long long r)
{
	long long  m = (l + r) >> 1, i, j, k;
	if (l == r) return;
	merge_sort2(l, m);
	merge_sort2(m + 1, r);
	for (i=l, j=m+1, k=l; i<=m || j<=r; )
		if (j > r || (i <= m && (client[cadr2[i]][0]*client[cadr2[j]][1] < client[cadr2[j]][0]*client[cadr2[i]][1])))
			B[k++] = cadr2[i++];
		else
			B[k++] = cadr2[j++];
	for (k = l; k <= r; k++) cadr2[k] = B[k];
}

int main()
{ifstream f("pachete.in");
 f>>n;
 f>>sediu[0]>>sediu[1];
 for(i=1;i<=n;i++)
  f>>client[i][0]>>client[i][1];
 for(i=1;i<=n;i++)
  {client[i][0]-=sediu[0];
   client[i][1]-=sediu[1];
   }

 for(i=1;i<=n;i++)
  {if(client[i][1]>0)
	 //este deasupra sediului
	  cadr1[++cadr1[0]]=i;
   else
	 if(client[i][1]<0)
	  {cadr2[++cadr2[0]]=i;
	   client[i][1]=client[i][1]*(-1);
	   }
	 else
	   if(client[i][1]==0)
		 {if(client[i][0]<sediu[0]&&!st)
			st++;
		  if(client[i][0]>sediu[0]&&!dr)
			dr++;
		  }
   }
 if(cadr1[0]) merge_sort(1,cadr1[0]);
 if(cadr2[0]) merge_sort2(1,cadr2[0]);
 memset(B,0,sizeof(B));
 for(i=1;i<=cadr1[0];i++)
  {nr++;
   while(client[cadr1[i]][0]*client[cadr1[i+1]][1]==client[cadr1[i+1]][0]*client[cadr1[i]][1])
	 i++;
   }
 for(i=1;i<=cadr2[0];i++)
   {nr++;
	while(client[cadr2[i]][0]*client[cadr2[i+1]][1]==client[cadr2[i+1]][0]*client[cadr2[i]][1])
	 i++;
   }
 nr=nr+st+dr;

 ofstream g("pachete.out");
 g<<nr;
 g.close();
 return 0;
}