Cod sursa(job #2002359)

Utilizator Neamtu_StefanStefan Neamtu Neamtu_Stefan Data 19 iulie 2017 15:28:34
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 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;
    while (lo<hi)
    {
        mi=lo+(hi-lo)/2;

        if (v[mi]>=x)
            hi=mi;
        else
            lo=mi+1;
    }
    mi=lo+(hi-lo)/2;
    if (v[mi] < x)
        mi--;
    return mi;
}

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;;
    for (int i=1;i<=l1;i++)
    {
        for (int j=i+1;j<=l2;j++)
        {
            nrtri+=(binara(v[i]+v[j],j+1,n-1)-j);
        }
    }

    fout << nrtri;

    return 0;
}