Cod sursa(job #806456)

Utilizator DaicuDaicu Alexandru Daicu Data 2 noiembrie 2012 21:08:36
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define nmax 800
using namespace std;
int v[nmax];
int n;
int nr;
void citire(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&v[i]);

}
int binsearch(int f,int l,int sum){
	int midd;
	while(f<=l){
		midd=(f+l)/2;
	if(v[midd]<=sum && (v[midd+1]>sum || midd+1>=n))
		return midd;
	if(v[midd]>sum)
		l=midd-1;
	else
		f=midd+1;
	}
}

int main(){
	freopen("ntri.in","r",stdin);
	freopen("ntri.out","w",stdout);
	citire();
	sort(v,v+n);
	for(int i=0;i<n-2;i++)
		for(int j=i+1;j<n-1;j++)
			nr+=binsearch(j+1,n,v[i]+v[j])-j;
	printf("%d",nr);
	return 0;
}