Cod sursa(job #311238)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 3 mai 2009 00:33:07
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE *f,*s;

long int n,i,j,q,st,dr,mj,nr;
long int v[505];

int main()
{
	f=fopen("nrtri.in","r");
	s=fopen("nrtri.out","w");

	fscanf(f,"%ld\n",&n);
	
	for(i=0;i<n;i++)
		fscanf(f,"%ld ",&v[i]);
	
	sort(v,v+n);
	
	for(i=0;i<=n/2;i++)
	{
		for(j=i+1;j<n;j++)
		{
		    st=j+1;
			dr=n-1;
			
			while(st<=dr)
			{
				mj=(st+dr)/2;
				
				if((v[mj]<=v[i]+v[j] && v[mj+1]>v[i]+v[j]) || (v[mj]<=v[i]+v[j] && mj==n-1))
				{
					nr++;
					break;
				}	
				else
				{
					if(v[mj]>v[i]+v[j])
						dr=mj-1;
					else
						st=mj+1;
				}					
			}	
		}			
	}
	
	fprintf(s,"%ld",nr);
	
	
	
	fclose(s);
	
	return 0;
}