Cod sursa(job #1185750)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 16 mai 2014 18:46:17
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define abs(x) ((x) > 0 ? (x) : (-x))

const int NMAX = 801;
int N, V[NMAX];

int isTriangle(int lat1, int lat2, int lat3)
{
	return lat1 + lat2 >= lat3 &&
	       lat1 + lat3 >= lat2 &&
	       lat2 + lat3 >= lat1;
}

int main()
{
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);

	int i, j;
	int count = 0;

	scanf("%d", &N);
	for (i = 0; i < N; ++i)
		scanf("%d", &V[i]);

	sort(V, V+N);

	for (i = 0; i < N - 2; ++i) {
		for (j = i + 1; j < N - 1; ++j) {
			int lower = lower_bound(V+j+1, V+N, abs(V[i] - V[j]))-V;
			int upper = upper_bound(V+j+1, V+N, V[i] + V[j])-V;

			if (lower == V[N - 1] &&
			    !isTriangle(V[i], V[j], V[N - 1]))
				continue;

			if (upper == V[N - 1] &&
			    !isTriangle(V[i], V[j], V[N - 1]))
				continue;

			if (lower == V[N - 1] && upper == V[N - 1])
				count++;
			else
				count += (upper - lower);
		}
	}
	printf("%d\n", count);

	return 0;
}