Cod sursa(job #7292)

Utilizator C_OvidiuCotletz Ovidiu C_Ovidiu Data 21 ianuarie 2007 13:21:15
Problema Pachete Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.84 kb
#include<fstream.h>

int long elimin[50003],key[50003],keyy[50003],key1[50003],i,j,c[50003][2],sursa[2],n,sus[50003],jos[50003],nr,B[50003];

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 && sus[i] < sus[j]))
			{keyy[k]=key[i];
			 B[k++] =sus[i++];}
		 else
			{keyy[k]=key[j];
			B[k++] = sus[j++];}
	for (k = l; k <= r; k++) {key[k]=keyy[k]; sus[k] = B[k];}
}




void gaseste_drum(int long i)
	 {elimin[key[i]]=1;
	 if(c[key[i]][0]>0)
	   {
	   for(j=i+1;j<=n;j++)
		  if(c[key[j]][0]>0&&c[key[j]][0]<=c[key[i]][0])
			gaseste_drum(j);
		if(j==n+1)
		  return;
		}
	  else{
		for(j=i+1;j<=n;j++)
		  if(c[key[j]][0]<=0&&c[key[j]][0]>=c[key[i]][0])
			gaseste_drum(j);
		if(j==n+1)
		  return;
		}
	  }



int main()
{ifstream f("pachete.in");
 f>>n;
 f>>sursa[0]>>sursa[1];
 for(i=1;i<=n;i++)
  {f>>c[i][0]>>c[i][1];
   c[i][0]-=sursa[0];
   c[i][1]-=sursa[1];
   if(c[i][1]>=0)
	 {sus[++sus[0]]=c[i][1];
	  key[sus[0]]=i;
	  //key[sus[0]]=i;
	  }
   else
	{c[i][1]*=(-1);

	 jos[++jos[0]]=c[i][1];
	 key1[jos[0]]=i;
	 }
   }
 n=sus[0];
 key[0]=n;
 merge_sort(1,sus[0]);
 memcpy(sus,key,sizeof(key));
 for(i=1;i<=sus[0];i++)
  key[sus[0]-i+1]=sus[i];
 for(i=1;i<=sus[0];i++)
  {
   if(!elimin[key[i]])
	{nr++;
	 gaseste_drum(i);
	 }
   }
 n=jos[0];
 merge_sort(1,n);
 memcpy(key,key1,sizeof(key1));
 key[0]=n;
 memcpy(sus,jos,sizeof(sus));
 merge_sort(1,n);
 memcpy(sus,key,sizeof(key));
 for(i=1;i<=sus[0];i++)
  key[sus[0]-i+1]=sus[i];
 for(i=1;i<=sus[0];i++)
  {
   if(!elimin[key[i]])
	{nr++;
	 gaseste_drum(i);
	 }
   }
 ofstream g("pachete.out");
 g<<nr;
 g.close();
 return 0;
 }