Cod sursa(job #1213612)

Utilizator rangerChihai Mihai ranger Data 28 iulie 2014 16:58:51
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int n,i,j,a[810],nrt=0;
int CautBin(int l,int r,int x)
{
    int m,poz=0;
    while (l<=r)
    {
       m=(l+r)/2;
       if (x>=a[m]) poz=m, r=m-1;
         else l=m+1;
    }
    return poz;
}
int main()
{
    cin>>n;
    for (i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for (i=1;i<=n-2;i++)
        for (j=i+1;j<=n-1;j++)
        { int x=CautBin(j+1,n,a[i]+a[j]);
         if (x)  nrt+=x-j;
        }
    cout<<nrt;
    return 0;
}