Cod sursa(job #1147423)

Utilizator andreiagAndrei Galusca andreiag Data 19 martie 2014 20:23:11
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <algorithm>

using namespace std;
const int Nmax = 805;

int N, cnt = 0, A[Nmax];

int main()
{
    ifstream f ("nrtri.in");
    ofstream g ("nrtri.out");

    f >> N;
    for (int i = 0; i < N; i++)
        f >> A[i];

    sort (A, A + N);
    if (N < 3) { g << 0 << '\n'; return 0; }

    for (int c = 2; c < N; c++) // cea mai mare latura are lungimea A[c];
    {
        for (int a = 0; a < c - 1; a++) // cea mai mica latura are lungimea A[a];
            cnt += A + c - lower_bound(A + a + 1, A + c, A[c] - A[a]);
    }
    g << cnt << '\n';
    return 0;
}