Cod sursa(job #113521)

Utilizator tvladTataranu Vlad tvlad Data 10 decembrie 2007 17:53:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 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);
	printf("\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 (st+step < n && a[st+step] < a[j]-a[i]) st += step;
			}
			for(step = 1; step <= n; step <<= 1); step >>= 1;
			int fi; for (fi = -1; step; step >>= 1) {
				if (fi+step < n && 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 intre %d si %d\n",a[i],a[j],cate,st,fi);
		}
	}
	r /= 3;
	printf("%d\n",r);
	return 0;
}