Cod sursa(job #1990118)

Utilizator PredunaTudorPreduna Tudor-Gabriel PredunaTudor Data 10 iunie 2017 15:54:59
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int n, bt[30000], tri = 0,j, temp, l = 0, r;

int main()
{
    in>>n;
    for (int i = 0; i < n; i++)
    {
        in>>bt[i];
    }

    for (int i = 0; i < n; i++)
    {
        j = i;
        while (j > 0 && bt[j-1] > bt[j])
        {

            temp = bt[j];
            bt[j] = bt[j-1];
            bt[j-1] = temp;
            j--;
        }
    }
    for(int i = 0; i < n - 2; i++)
    {
        for(int j = i + 1; j < n - 1; j++)
        {
            l = j + 1;
            r = n;
            while(l <= r)
            {
                temp = (l + r) / 2;
                if(bt[temp] < bt[i] + bt[j])
                {
                    l = temp + 1;
                }
                else
                    r = temp - 1;

            }
            if(bt[r] < bt[i] + bt [j])
            tri += r - j;
        }
    }
    cout<<tri;
}