Cod sursa(job #3207814)

Utilizator SankeAndrei Lascu Sanke Data 27 februarie 2024 00:11:39
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int countTriangles(vector<int>& sticks) {
    int n = sticks.size();
    int count = 0;

    sort(sticks.begin(), sticks.end(), greater<int>());

    for (int i = 0; i < n - 2; ++i) {
        int k = i + 2;
        for (int j = i + 1; j < n - 1; ++j) {
            while (k < n && sticks[i] < sticks[j] + sticks[k]) {
                ++k;
            }
            count += k - j - 1;
        }
    }

    return count;
}

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

    int N;
    fin >> N;

    vector<int> sticks(N);

    for (int i = 0; i < N; ++i) {
        fin >> sticks[i];
    }

    int result = countTriangles(sticks);

    fout << result << endl;

    fin.close();
    fout.close();

    return 0;
}