Cod sursa(job #1760304)

Utilizator KusikaPasa Corneliu Kusika Data 20 septembrie 2016 17:37:17
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

vector <int> bat;

int binsearch(int L, int R, int x)
{
    int ras = -1;
    while (L <= R)
    {
        int mid = (L+R)/2;
        if (x < bat[mid]) R = mid - 1;
        else if (x > bat[mid]) L = mid + 1;
        else if (bat[mid+1] == bat[mid]) L = mid + 1;
        else {ras = mid; break;}
    }

    if (ras < 0) return L-1;
    else return ras;
}

int main()
{
    int n, ras=0;

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

    sort(bat.begin(),bat.end());

    for (int i = 0; i < n-2; i++)
        ras += binsearch(i+1,n-1,bat[i]+bat[i+1]) - i - 1;


    fout << ras;
    return 0;
}