Cod sursa(job #2119555)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 1 februarie 2018 13:59:04
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n, i, v[3001], s, sol, st, dr, j, mid;
int main()
{
    fin >> n;
    for (i=1; i<=n; i++){
        fin >> v[i];
    }
    sort (v + 1, v + n + 1);
    for (i=1; i<=n-2; i++){
        for (j=i+1; j<=n-1; j++){
            s = v[i] + v[j];
            st = j+1;
            dr = n;
            while (st <= dr){
                mid = (st+dr)/2;
                if (v[mid] <= s){
                    sol++;
                    break;
                }
                if (s > v[mid])
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
        }
    }
    fout << sol;
    return 0;
}