Cod sursa(job #272636)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 7 martie 2009 16:08:02
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <stdlib.h>

const int N = 802;

int n,v[N],nrt=0;

void citire()
{
	scanf ("%d",&n);
	for (int i = 1; i <= n; ++i)
		scanf ("%d",&v[i]);
}

int comparare (const void *p, const void *q)
{
	int x = *(int*)p, y = *(int*)q;
	if (x < y)
		return -1;
	if (x > y)
		return 1;
	return 0;
}

void sortare()
{
	qsort(v+1,n,sizeof(v[0]),comparare);
}

void cautare()
{
	int i,j,k;
	for (k = 3; k <= n; ++k)
		if (v[k]>v[1]+v[2])
			break;
	//--k;
	//nrt += k - j;
	v[n+1] = 100000;
	for (i = 1; i <= n-2; ++i)
		for (j = i+1; j <= n-1; ++j)
		{
			for (k = j + 1; k <= n+1; ++k)
				if (v[k] > v[i]+v[j])
					break;
			nrt += k - j - 1;
		}
}

void afisare()
{
	printf ("%d",nrt);
}

int main()
{
	freopen ("nrtri.in","r",stdin);
	freopen ("nrtri.out","w",stdout);
	citire();
	sortare();
	cautare();
	afisare();
}