Cod sursa(job #237664)

Utilizator DraStiKDragos Oprica DraStiK Data 30 decembrie 2008 13:14:22
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#include <algorithm>
using namespace std;  
int a[805];
int n,nrt;
int cautbin (int val,int in)
{
    int sf=n,mij;
    while (in<=sf)
    {
        mij=in+(sf-in)/2;
        if ((a[mij]<=val && a[mij+1]>val) || (mij==n && a[mij]<=val))
            return mij;
        else if (a[mij]<val)
			in=mij+1;
		else
			sf=mij-1;
	}
}
int main ()
{
	freopen ("nrtri.in","r",stdin);
	freopen ("nrtri.out","w",stdout);
	int i,j;
	scanf ("%d",&n);
	for (i=1; i<=n; ++i)
		scanf ("%d",&a[i]);
	sort (a+1,a+n+1);
	for (i=1; i<=n-2; ++i)
		for (j=i+1; j<=n-1; ++j)
            nrt+=cautbin (a[i]+a[j],j)-j;
    printf ("%d",nrt);
    return 0;
}