Cod sursa(job #2281567)

Utilizator braresBirzaneanu Rares brares Data 12 noiembrie 2018 14:56:56
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<fstream>

using namespace std;
int v[1001];
int n,i,j, st, dr, aux, x, sol;
int main()
{
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];

    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++)
            if (v[i] > v[j]) {
                aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }
    /// stabilim intai laturile mai mici ale triunghiului
    for (i=1;i<=n-2;i++)
        for (j=i+1;j<=n-1;j++) {
            /// a treia latura trebuie sa fie dupa pozitia j
            /// si cu valoarea strict mai mica decat v[i]+v[j]
            x = v[i] + v[j];
            /// intre pozitiile j+1 si n caut ultima valoare strict mai mica decat x
            st = j+1;
            dr = n;
            /// valori strict mai mici decat x inseamna 0 (in imaginatia noastra)
            /// celelalte, adica mai mari sau egale cu x inseamna 1
            while (st <= dr) {
                int mid = (st+dr)/2;
                if (v[mid] < x)
                    st = mid+1;
                else
                    dr = mid-1;
            }
            sol += dr-j; /// orice valoare de dupa j si pana la ce am gasit in cb este o buna a treia latura
        }
    fout<<sol;
    return 0;
}