Cod sursa(job #2908103)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 1 iunie 2022 14:35:32
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

unsigned int vec[800];

void QuickSort(unsigned int* arr, unsigned int num) {
    if(num < 2)
        return;

    unsigned int pivot = arr[0];
    unsigned int arr1[800], arr2[800];
    unsigned int num1 = 0, num2 = 0;

    for(unsigned int i = 1; i < num; ++i)
        if(arr[i] < pivot)
            arr1[num1++] = arr[i];
        else
            arr2[num2++] = arr[i];
    
    QuickSort(arr1, num1);
    QuickSort(arr2, num2);

    unsigned int ind = 0;
    for(unsigned int i = 0; i < num1; ++i)
        arr[ind++] = arr1[i];
    arr[ind++] = pivot;
    for(unsigned int i = 0; i < num2; ++i)
        arr[ind++] = arr2[i]; 
}
int main() {
    std::ifstream fin("nrtri.in");
    std::ofstream fout("nrtri.out");

    unsigned int n;
    fin >> n;

    for(unsigned int i = 0; i < n; ++i)
        fin >> vec[i];
    QuickSort(vec, n);

    unsigned int num = 0;
    for(unsigned int i = 0; i < n - 2; ++i) {
        unsigned int sum = vec[i] + vec[i + 1];

        for(unsigned int j = i + 2; j < n && sum >= vec[j]; ++j)
            ++num;
    }
    fout << num;

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

    return 0;
}