Cod sursa(job #1894433)

Utilizator luanastLuana Strimbeanu luanast Data 26 februarie 2017 20:29:35
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int n, i, j, mid, p, u, s, sol, soll;
int v[301];

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

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

    fout << sol;

    return 0;
}