Cod sursa(job #528378)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 2 februarie 2011 18:24:39
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream.h>
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[801],aux[801],c,ok,m,st,dr,nr,poz;
void interclas(int i,int m,int j)
{ int x=i,y=m+1,k=1,t=i;
  while(x<=m&&y<=j)
	  if(v[x]<v[y]) aux[k++]=v[x++];
		  else aux[k++]=v[y++];
  while(x<=m) aux[k++]=v[x++];
  while(y<=j) aux[k++]=v[y++];
  for(k=1;k<(j-i)+2;k++) v[t++]=aux[k];
}

void divimp(int i,int j)
{ if(i<j)
	{int m=i+(j-i)/2;
	 divimp(i,m);
	 divimp(m+1,j);
	 interclas(i,m,j);
	}
}

int main()
{ int i,j,k;
  f>>n;
  for(i=1;i<=n;i++) f>>v[i];
  divimp(1,n);
  for(k=3;k<=n;k++)
	  {j=k-1;
	   while(j>1)
		   {c=v[k]-v[j];
		    st=1; dr=j-1; ok=0;
			while(st<=dr&&!ok)
				{m=(st+dr)/2;
				 if(v[m]==c) ok=1,poz=m;
					 else if(v[m]<c) st=m+1;
							 else dr=m-1;
				}
			if(m>=j) m=j-1;
			while(v[m]<c&&m<j) m++;
			while(v[m-1]>=c&&m>1) m--;
			nr=nr+j-m;
			j--;
		   }
	  }
  g<<nr<<'\n';
  f.close(); g.close();
  return 0;
}