Cod sursa(job #311855)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 4 mai 2009 15:18:02
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE *f,*s;

long int n,i,j,k,v[1000],rez;

int cautare(int x, int y)
{
	int st=x,dr=y,mj;
	
	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))
		{
			printf("%d %d %d\n",i+1,j+1,mj+1);
			return mj;
		}	
		else
		{
			if(v[mj]<=v[i]+v[j] && v[mj+1]<=v[i]+v[j])
				st=mj+1;
			else
				dr=mj-1;
		}	
	}

	return 0;	
}


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++)
		{
			k=cautare(j+1,n-1);
			
			if(k!=0)
			{
				k-=j;
				rez+=k;
			}
		}	
	}		
	
    fprintf(s,"%ld",rez); 
	
	fclose(s);
	
	return 0;
}