Cod sursa(job #2026668)

Utilizator lucaignatescuIgnatescu Luca lucaignatescu Data 24 septembrie 2017 20:35:18
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 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 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;
}