Cod sursa(job #3207818)

Utilizator SankeAndrei Lascu Sanke Data 27 februarie 2024 00:20:05
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

vector<int> v;

int main() {
    // Dezactivează sincronizarea între fluxurile C și C++ pentru a îmbunătăți performanța.
    ios::sync_with_stdio(false);
    // Dezactivează sincronizarea dintre cin și cout.
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    // Inițializează vectorul și citeste lungimile betisoarelor.
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    // Sortează vectorul în ordine crescătoare.
    sort(v.begin() + 1, v.end());

    int nr1, nr2, nr3;
    int cont = 0; // Contorul pentru numărul de triunghiuri.

    // Parcurge posibilele triplete de lungimi de betisoare.
    for (int i = 1; i <= n - 2; i++) {
        nr1 = i;
        for (int j = i + 1; j <= n - 1; j++) {
            nr2 = j;
            nr3 = j + 1;

            // Găsește poziția celei de-a treia lungimi care satisface condiția de existență a triunghiului.
            while (nr3 < n && v[nr3] <= v[nr1] + v[nr2]) {
                nr3 += 1;
            }

            // Actualizează contorul cu numărul de triunghiuri posibile găsite în această iterație.
            cont += nr3 - nr2 - (v[nr3] > v[nr1] + v[nr2]);
        }
    }

    // Afișează rezultatul.
    cout << cont;

    return 0;
}