Cod sursa(job #1956022)

Utilizator DavidLDavid Lauran DavidL Data 6 aprilie 2017 13:49:12
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("nrtri.in");
ofstream fo("nrtri.out");

int i,j,X[801],n,cnt,rez;

int cautare_binara()
{
    ///cautam pe Xi+Xj=x in X
    int x=X[i]+X[j];
    int st=j+1,dr=n+1,mij;
    while (dr-st>1)
    {
        mij=(st+dr)/2;
        if (x<X[mij])
            dr=mij;
        else
         st=mij;
    }
    return st;
}

int main()
{
    fi>>n;
    for (i=1; i<=n; i++)
        fi>>X[i];
    sort(X+1,X+n+1);
    for (i=1; i<=n-2; i++)
        for (j=i+1; j<=n-1; j++)
        {
            ///cautam binar pe Xi+Xj in X; rez=ultimul element cu care se poate face triunghi
            rez=cautare_binara();
            cnt+=(rez-j);
        }
    fo<<cnt;
    fi.close();
    fo.close();
    return 0;
}