Cod sursa(job #235596)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 24 decembrie 2008 16:31:39
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<cstdio>
#include<algorithm>

using namespace std;

int v[801],i,j,n,k;

int bsearch(int s,int d)
{       int m;k=0;
        m=(s+d)/2;
        while(s<=d)
                if((v[m]<=v[i]+v[j]&&v[m+1]>v[i]+v[j])||(v[m]<=v[i]+v[j]&&m==n))
                        return m-j+1;
                else    if(v[m]<=v[i]+v[j]&&v[m+1]<=v[i]+v[j])
                                {s=m+1;m=(s+d)/2;}
                        else{d=m-1;m=(s+d)/2;}
        return 0;
}
int main()
{       freopen("nrtri.in","r",stdin);
        freopen("nrtri.out","w",stdout);
        scanf("%d",&n);
        for(i=1;i<=n;i++)
                scanf("%d",&v[i]);
        sort(v+1,v+n+1);
        for(i=1;i<=n-2;i++)
                for(j=i+1;j<=n-1;j++)
                       k+=(bsearch(j+1,n));
        printf("%d\n",k);
        return 0;
}