Cod sursa(job #235598)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 24 decembrie 2008 16:43:35
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
#include<algorithm>

using namespace std;

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

int bsearch(int s,int d)
{       int m;
        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;
                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;
}