Cod sursa(job #1396808)

Utilizator bluespideyMarin Diana bluespidey Data 23 martie 2015 00:19:02
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,i,nr,j,a,e,r,l,m,v[801],b,c,d,sum;

int mod(int f)
{
    if(f<0)
        f*=(-1);
    return f;
}


int main()
{
    fin >> n;

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

    sort(v+1,v+n+1);

    for(i = 1; i <= n;++i)
        for(j = i + 1; j <= n; ++j)
            {
                a = mod(v[i]-v[j]);
                b = v[j]+v[i];

                l = 1;
                r = n;
                while(l <= r)
                {
                   m = l + (r-l) / 2;
                   if(v[m] >= a)
                        {
                            d = m;
                            r = m - 1;
                        }
                    else l = m + 1;
                }


                r = n;
                l = 1;

                while(l <= r)
                {
                   m = l + (r-l) / 2;
                   if(v[m] <= b)
                        {
                            e = m;
                            l = m + 1;
                        }
                    else r = m - 1;
                }

                if(e-d-1>0)
                    nr+=e-d-1;

            }
    fout << nr/2;

    return 0;
}