Cod sursa(job #1990111)

Utilizator PredunaTudorPreduna Tudor-Gabriel PredunaTudor Data 10 iunie 2017 15:37:17
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 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; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            l = j + 1;
            r = n - 1;
            while(l < r){
                temp = (l + r) / 2;
                if(bt[temp] < bt[i] + bt[j])
                    {
                        l = temp + 1;
                    }
                    else
                        r = temp - 1;

            }
            tri = tri + r - j;

        }
    }



    /* for(int i = 0; i < n; i++)
        cout<<bt[i]<<" "; */

    out<<tri;
}