Cod sursa(job #130043)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 30 ianuarie 2008 23:30:49
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

long sol, n, i, a, b, c, v[810], t1, t2, mid, ok1, ok2;

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

long cbinar1(long nr1, long nr2) {
	long aux1 = nr1, aux2 = nr2, poz_bn = 0;
	while (aux1 < aux2) {
		mid = (aux1 + aux2) / 2;
		if (v[mid] <= v[a] + v[b] && v[mid] + v[a] >= v[b] && v[mid] + v[b] >= v[a]) {
			poz_bn = mid;
			aux2 = mid - 1;
		} else {
			aux1 = mid + 1;
		}
		ok1 = 1;
	}
	return poz_bn;
}

long cbinar2(long nr1, long nr2) {
	long aux1 = nr1, aux2 = nr2, poz_bn = 0;
	while (aux1 < aux2) {
		mid = (aux1 + aux2) / 2;
		if (v[mid] <= v[a] + v[b] && v[mid] + v[a] >= v[b] && v[mid] + v[b] >= v[a]) {
			poz_bn = mid;
			aux1 = mid + 1;
		} else {
			aux2 = mid - 1;
		}
		ok2 = 1;
	}
	return poz_bn;
}

int main() {
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &v[i]);
	}
	qsort(v + 1, n, sizeof(v[0]), cmp);
	for (a = 1; a <= n; ++a) {
		for (b = a + 1; b <= n; ++b) {
			if (b + 1 == n) {
				if (v[n] <= v[a] + v[b] && v[n] + v[a] >= v[b] && v[n] + v[b] >= v[a]) {
					++sol;
				}
			}
			if (b + 1 < n) {
				t1 = cbinar1(b + 1, n);
				t2 = cbinar2(b + 1, n);
				sol += t2 - t1 + 1;
			}
		}
	}
	printf("%ld", sol);
	return 0;
}