Cod sursa(job #445913)

Utilizator voikybodea voichita voiky Data 24 aprilie 2010 14:38:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream.h>

int n,x[801],nr,y[801];

void inter(int st,int m,int dr)
{
	int k=st,i=st,j=m+1;
	while(i<=m && j<=dr)
		if(x[i]<=x[j])y[k++]=x[i++];
		else y[k++]=x[j++];
	while(i<=m)y[k++]=x[i++];
	while(j<=dr)y[k++]=x[j++];
	for(i=st;i<=dr;i++)x[i]=y[i];
}

void sort(int st,int dr)
{
	if(st<dr)
	{
		int m=st+(dr-st)/2;
		sort(st,m);sort(m+1,dr);
		inter(st,m,dr);
	}
}

int caut(int st,int dr,int z)
{
	while(st<dr)
	{
		int m=st+(dr-st)/2;
		if(z>=x[m])st=m+1;
		else dr=m-1;
	}
	if(z>=x[st])return st;
	return st-1;
}

int main()
{
	  ifstream f("nrtri.in");ofstream g("nrtri.out");
	  int i,j,s=0;
	  f>>n;for(i=1;i<=n;i++)f>>x[i];
	  sort(1,n);
	  for(i=1;i<=n-2;i++)
		  for(j=i+1;j<=n-1;j++)
			  {
				  s=caut(j+1,n,x[i]+x[j]);
				  if(s)nr=nr+(s-j);
			  }		  
	  g<<nr;		  
	  f.close();g.close();
	  return 0;
}