Cod sursa(job #899059)

Utilizator mvcl3Marian Iacob mvcl3 Data 28 februarie 2013 12:44:26
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<cstdio>
#include<algorithm>
using namespace std;

const int NMAX = 809;
int n, nrtri, v[NMAX];

int main()
{
    freopen("nrtri.in", "rt", stdin); freopen("nrtri.out", "wt", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);

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

    for(int i = 1; i <= n - 2; ++i)
    {
        int x = lower_bound(v + i + 3, v + n + 1, v[i] + v[i + 1] + 1) - v;
        int y = i + 2;
        x--;
        if(x == y)
        {
            if(v[i] + v[i + 1] >= v[x])
                ++nrtri;
        }
        else nrtri += x - y + 1;
    }

    printf("%d\n", nrtri);
}