Cod sursa(job #58621)

Utilizator andrei.12Andrei Parvu andrei.12 Data 6 mai 2007 17:16:57
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#include<stdlib.h>
int a, b, j, v[801], nr, n;
int comp(const void*x, const void*y)
{
	int *xx=(int*)x, *yy=(int*)y;
	int xxx=*xx, yyy=*yy;
	if (xxx<yyy) return -1;
	if (xxx>yyy) return 1;
	return 0;
}
int bs(){
	int li=j+1, ls=n, t;
	while (li<=ls){
		t=(li+ls)/2;
		if (v[t]>a+b)
			ls=t-1;
		else 
		if (v[t+1]>a+b)
			return t;
		else 
			if (v[t+1]==a+b)
				return t+1;
			else 
				li=t+1;
	}
	return 0;
}
int main()
{
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	int i, poz;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&v[i]);
	qsort(v,n+1,sizeof(v[0]),comp);
	v[n+1]=30001;
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			a=v[i];
			b=v[j];
			poz=bs();
			if (poz==0) break;
			else nr+=poz-j;
		}
	printf("%d\n",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}