Cod sursa(job #541143)

Utilizator Carl896Carl Adam Carl896 Data 24 februarie 2011 20:57:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include "stdio.h"

int v[800];

inline int IsTriangle(int a, int b, int c)
{
	if(a > (b + c) ||
		b > (a + c) ||
		c > (a + b))
	{
		return 0;	//not triangle
	}

	return 1; //is triangle
	
}

int main()
{
	FILE *f,*g;
	int n,m,opt,x;
	int i,j,k;
	int counter=0;
	int rez;
	int temp;
	int st,dr;
	f = fopen("nrtri.in","r");
	g = fopen("nrtri.out","w");
	
	fscanf(f,"%d ",&n);
	
	i=0;
	while(i<n)
	{
		fscanf(f,"%d ",&v[i]);	
		i++;
	}
	
	
	for(i=0;i<(n-1);i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(v[i]>v[j])
			{
				temp = v[i];
				v[i] = v[j];
				v[j] = temp;
			}
		}
	}

	
	for(i=0;i<(n-2);i++)
	{
		for(j=i+1;j<(n-1);j++)
		{
			//binary search
			//k = (j + n)/2;
			st = j+1;
			dr = n-1;
			if(st==dr)
			{
				if(IsTriangle(v[i],v[j],v[dr]))
				{
					counter++;
				}
				continue;
			}
			while(st<dr)
			{
				if(IsTriangle(v[i],v[j],v[dr]))
				{
					st = (dr + st) / 2;
				}
				else
				{
					dr = (dr + st) / 2;
				}
			}
			counter += st - j;
		}
	}
	fprintf(g,"%d",counter);

	fclose(f);
	fclose(g);

	return 0;
}