Cod sursa(job #209088)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 20 septembrie 2008 15:09:24
Problema Numarare triunghiuri Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <cstdlib>
int nr,i1,i2,i3,n,v[850],p;
int comp(const void *a, const void *b){
	int aa=*(int*)a,bb=*(int*)b;
	if (aa>bb)
		return 1;
	if (aa<bb)
		return -1;
	return 0;
}
void read(){
	int i;
	freopen("nrtri.in","r",stdin);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		scanf("%d",&v[i]);
	qsort(v,n+1,sizeof(v[0]),comp);
}
int bsearch(int p,int u){
	int m;
	while(p!=u){
		m=(p+u)/2;
		if (v[i1]+v[i2]<=v[m])
			u=m;
		else
			p=m+1;
	}
	if(v[p]>v[i1]+v[i2])
		--p;
	return p;
}
void solve(){
	for (i1=1;i1<=n-2;++i1)
		for (i2=i1+1;i2<=n-1;++i2){
			p=bsearch(i2+1,n);
			/*
			for(int i=i2+1;i<=p;++i)
				printf("(%d,%d,%d)\n",v[i1],v[i2],v[i]);
			*/
			nr+=(p-i2);
		}
}
void write(){
	freopen("nrtri.out","w",stdout);
	printf("%d\n",nr);
}
int main(){
	read();
	solve();
	write();
}