Cod sursa(job #2255382)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 6 octombrie 2018 20:19:05
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
const int MAX_SIZE = 1002;
int binarySearch(int x[], int n, int i, int j){
    int left = j + 1, right = n, middle, value = x[i] + x[j];
    while(left <= right){
        middle = (left + right) / 2;
        if(x[middle] <= value)
            left = middle + 1;
        else
            right = middle - 1;
    }
    return right;
}
int main()
{
    int n, x[MAX_SIZE], result = 0, third;
    in>>n;
    for(int i=1;i<=n;i++)
        in>>x[i];
    in.close();
    sort(x+1,x+n+1);
    for(int i=1;i<=n-2;i++)
        for(int j=i+1;j<=n-1;j++){
            third = binarySearch(x,n,i,j);
            if(third > j)
                result += (third - j);
        }
    out<<result<<"\n";
    out.close();
    return 0;
}