Cod sursa(job #237622)

Utilizator DraStiKDragos Oprica DraStiK Data 30 decembrie 2008 11:19:26
Problema Numarare triunghiuri Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 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)
            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;
}