Cod sursa(job #2609844)

Utilizator Zamfirescuste2Zamfirescu Stefan Zamfirescuste2 Data 3 mai 2020 17:18:26
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int main(){

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

    int n;
    int v[801];

    f >> n;
    for( int i = 0; i < n; ++i)
        f >> v[i];

    sort(v, v + n);


    int nr_tri = 0;
    for( int i = 0; i < n - 2; ++i)
    {
        for(int j = i + 1; j < n - 1; ++j)
        {
            int st = j + 1;
            int dr = n - 1;
            int sol = -1;
            while ( st <= dr ){
                int mid = (st + dr) / 2;
                if ( v[i] + v[j] < v[mid])
                    dr = mid - 1;
                else
                    if ( mid == n - 1 && (v[i] + v[j] >= v[mid]))
                    {
                        sol = mid;
                        break;
                    }
                    else
                        if ( v[i] + v[j] >= v[mid] && v[i] + v[j] < v[mid + 1])
                        {
                            sol = mid;
                            break;
                        }
                        else
                            st = mid + 1;

            }
            if ( sol != -1 ) {
                nr_tri += sol - j;
            }
        }
    }
    cout << nr_tri << "\n";
    return 0;
}