Cod sursa(job #113514)

Utilizator tvladTataranu Vlad tvlad Data 10 decembrie 2007 17:36:28
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1000;

int n;
int a[N];

int main() {
	freopen("nrtri.in","rt",stdin);
	freopen("nrtri.out","wt",stdout);
	scanf("%d",&n);
	for (int i = 0; i<n; ++i) {
		scanf("%d",&a[i]);
	}
	sort(a,a+n);
	int r = 0;
	for (int i = 0; i<n; ++i) {
		for (int j = i+1; j<n; ++j) {
			int step; for(step = 1; step < n; step <<= 1); step >>= 1;
			int st; for (st = -1; step; step >>= 1) {
				if (a[st+step] < a[j]-a[i]) st += step;
			}
			for(step = 1; step < n; step <<= 1); step >>= 1;
			int fi; for (fi = 0; step; step >>= 1) {
				if (a[fi+step] <= a[j]+a[i]) fi += step;
			}
			int cate = fi-st;
			if (a[i] >= a[j]-a[i]) --cate;
			if (a[j] >= a[j]-a[i]) --cate;
			r += cate;
//			printf("la laturile %d si %d se potrivesc %d\n",a[i],a[j],cate);
		}
	}
	r /= 3;
	printf("%d\n",r);
	return 0;
}