Cod sursa(job #1889226)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 22 februarie 2017 17:12:15
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 800

int n, result;
int v[MAXN];

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

void print()
{
	printf("%d\n",result);
}

int cmp (const void *a, const void *b)
{
	return *((int *) a) - *((int *) b);
}

void compute()
{
	qsort(v,n,sizeof(int),cmp);
	for (int k = n - 1; k > 1; --k) {
		int i = 0, j = k - 1;
		while (i < j) {
			int sum = v[i] + v[j];
			if (sum >= v[k]) {
				result += j - i;
				--j;
			} else {
				++i;
			}
		}
	}
}

int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	read();
	compute();
	print();
	return 0;
}