Cod sursa(job #1939420)

Utilizator bostanmateiBostan Matei-Calin bostanmatei Data 25 martie 2017 18:41:26
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <algorithm>
#define NMAX 805

using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n, i, j, st, dr, mij, nrtri, v[NMAX];

int main()
{
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> v[i];

    // sortam numerele pentru a aplica cautarea binara pe rezultat
    sort(v + 1, v + n + 1);
    /// alegem primele 2 laturi si cautam binar a treia latura (vezi //(~*~)//)
    for(i = 1; i < n - 1; i++)
        for(j = i + 1; j < n; j++)
        {
            st = j + 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;                //(~*~)//
                if(v[mij] <= v[i] + v[j])   // intr-un triunghi suma a 2 laturi
                    st = mij + 1;           // e mai mare deca a treia
                else                        /// egalul e o exceptie(la precizari) :)
                    dr = mij - 1;

                nrtri += dr - j;
            }
        }
    fout << nrtri << '\n';
}