Cerința

Se dau n numere naturale distincte. Determinaţi câte triunghiuri distincte pot avea lungimile laturilor printre aceste numere.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n numere naturale.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând numărul de triunghiuri determinate.

Restricții și precizări

• 1 ≤ n ≤ 1000
• cele n numere citite vor fi mai mici decât 1.000.000
• dacă ați rezolvat probleme #Triunghiuri ^[100] , ați văzut deja că aici n este mai mare

Exemplu

Intrare

5
3 5 10 7 6 

Ieșire

7

Explicație

Cele 7 triunghiuri au lungimile laturilor:
3 5 7
3 5 6
3 7 6
5 7 6
5 10 7
5 10 6
10 7 6

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, cnt = 0, a, b;
    int lat[1001];
    cin >>n;
    for (int i =1; i<=n; i++)
    {
        cin >> lat[i];
    }
    sort(lat + 1 , lat + n + 1);
    for (int i = 1 ; i <= n - 2 ; i++)
    {
        for (int j  = i + 1 ; j <= n - 1 ; j++)
        {
            a = lat[i];
            b = lat[j];
            int dr = n, st = j + 1, mij;
            while (dr >= st)
            {
                mij = (dr + st)/2;
                if (lat[mij] < a + b )
                    st = mij + 1;
                else 
                    dr = mij - 1;
            }
            cnt += dr - j;
        }
    }
    cout << cnt;
    return 0;
}