Cod sursa(job #1799886)

Utilizator horatiucheval2Horatiu Andrei Cheval horatiucheval2 Data 6 noiembrie 2016 22:29:14
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <iostream>
#include <fstream>

void mergeSubarrays(int arr[], int left, int mid, int right){
    int i = left, j = mid + 1;
    int temp[1000], len = 0;

    while(i <= mid && j <= right){
        if(arr[i] < arr[j]){
            temp[len++] = arr[i++];
        }else{
            temp[len++] = arr[j++];
        }
    }

    for(; i <= mid; i++){
        temp[len++] = arr[i];
    }

    for(; j <= right; j++){
        temp[len++] = arr[j];
    }

    for(int i = 0; i < len; i++){
        arr[left + i] = temp[i];
    }
}

void mergeSort(int arr[], int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        mergeSubarrays(arr, left, mid, right);
    }
}


// Cauta binar in intervalul arr[left] ... arr[right] inclusiv primul element care este mai mare decat val si ii returneaza pozitia.
int binarySearch(int arr[], int left, int right, int val){
    int mid = (left + right) / 2;

    if(left == right){
        if(!(arr[left] > val)){
            return right + 1;
        }else{
            return left;
        }
    }

    if(arr[mid] > val){
        return binarySearch(arr, left, mid, val);
    }else{
        return binarySearch(arr, mid + 1, right, val);
    }

}

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

    int n, v[1000], k = 0;
    fin >> n;
    for(int i = 0; i < n; i++){
        fin >> v[i];
    }

    mergeSort(v, 0, n - 1);

    //std::cout << binarySearch(v, 0, n - 1, v[5] + v[7]);

    for(int i = 0; i < n - 2; i++){
        for(int j = i + 1; j < n - 1; j++){
            k += binarySearch(v, j + 1, n - 1, v[i] + v[j]) - 1 - j;
            //std::cout << k << " ";
        }
    }

    fout << k;

    fin.close();
    fout.close();
    return 0;
}