Cod sursa(job #1347718)

Utilizator Vele_GeorgeVele George Vele_George Data 19 februarie 2015 09:42:56
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> v;
int cb(int st, int dr, int sum)
{
    int mid;
    while(dr-st>1)
    {
        mid=(st+dr)/2;
        //cout << mid << " ,";
        if (v[mid]<=sum) st=mid;
                     else dr=mid;
    }
    //cout << "\n";
    return st;
}


int main()
{
    int n,x;
    ifstream f("nrtri.in");
    ofstream g("nrtri.out");

    f >> n;
    for(int i=0; i<n; i++)
    {
        f >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end());
    int k=0,aux;
    for(int i=0; i<n-2; i++)
    {
        for(int j=i+1; j<n-1; j++)
        {
            aux=cb(j-1,n,v[i]+v[j]);
            if (aux!=j-1) k+=aux-j;
        }
    }
    g << k;

    f.close();
    g.close();
    return 0;
}