Cod sursa(job #2027725)

Utilizator lucaignatescuIgnatescu Luca lucaignatescu Data 26 septembrie 2017 17:21:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in ("nrtri.in");
ofstream out ("nrtri.out");

//int cautareBinara(int x,int y,int *v,int n)
//{
//    int st=y+1;
//    int dr=n;
//    int m=(st+dr)/2;
//    int s=v[x]+v[y];
//    if(st==dr&&v[m]<=s)
//        return m-y;
//    while(st<dr)
//    {
//        if(v[m]==s)
//            return m-y;
//        if(v[m]<s)
//            st=m+1;
//        else
//            dr=m-1;
//        m=(st+dr)/2;
//    }
//    return m-y-1;
//}

int cautareBinara(int i,int j,int *v,int n)
{
    int st=j+1,dr=n,m,s=v[i]+v[j];
    int sol=-1;
    while(st<=dr)
    {
        m=(st+dr)/2;
        if(v[m]<=s)
        {
            st=m+1;
            sol=m;
        }
        else
            dr=m-1;
    }
    if(sol==-1)
        return 0;
    return sol-j;
}

int main()
{
    int n,v[805],s=0;
    in>>n;
    for(int i=1;i<=n;++i)
    {
            in>>v[i];
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=n-2;++i)
        for(int j=i+1;j<=n-1;++j)
    {
        s+=cautareBinara(i,j,v,n);
    }
    out<<s;
    return 0;
}