Cod sursa(job #2002368)

Utilizator Neamtu_StefanStefan Neamtu Neamtu_Stefan Data 19 iulie 2017 15:54:19
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;

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

int n,v[802];

void quicksort(int start, int stop)
{
    int i=start,j=stop,nr;

    nr=v[(i+j)/2];

    do
    {
        while (i<stop && nr>v[i]) ++i;
        while (j>start && nr<v[j]) --j;

        if (i<=j)
            swap(v[i++],v[j--]);
    }while(i<=j);

    if (j>start) quicksort(start,j);
    if (i<stop) quicksort(i,stop);
}

int binara(int x, int lo, int hi)
{
    int mi,sol=0;
    while (lo<=hi)
    {
        mi=lo+(hi-lo)/2;

        if (v[mi]>x)
            hi=mi-1;
        else
        {
            lo=mi+1;
            sol=mi;
        }
    }

    return sol;
}

int main()
{
    fin >> n;
    for (int i=1;i<=n;i++)
        fin >> v[i];

    quicksort(1,n);

    int nrtri=0,l1=n-2,l2=n-1,nr;
    for (int i=1;i<=l1;i++)
    {
        for (int j=i+1;j<=l2;j++)
        {
            int sol=binara(v[i]+v[j],j+1,n);
            if (sol)nrtri+=sol-j;
        }
    }

    fout << nrtri;

    return 0;
}