Cod sursa(job #2678073)

Utilizator bibiancapitu2004Pitu Bianca bibiancapitu2004 Data 28 noiembrie 2020 08:53:18
Problema Numarare triunghiuri Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include<algorithm>
using namespace std;

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

int l[805] , n;
int lowerBound(int target){

    int s=0, h=n, mid;

    while(s< h){
        int mid = (s+h)/2;
        if(l[mid] >= target)
            h = mid;
        else
            s = mid+1;
    }

    return h;
}



int main()
{
    int nr = 0;
    in >> n;
    for(int i = 0;i < n;i ++)
        in >>l[i];
    sort(l,l + n);
    for(int i = 0;i <n - 2;i ++)
    {
        for(int j = i + 1;j < n - 1 ;j ++)
        {
            int x = lowerBound(l[i] + l[j]);
            if(x == n)
              x --;
            else if(l[x] != l[i] + l[j])
              x --;
            if(x == n)
              x --;
            nr += x - j;

        }
    }
    out << nr;


    return 0;
}