Cod sursa(job #1760309)

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

using namespace std;

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

//ifstream fin("in.txt");
//ofstream fout("out.txt");

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;

    long 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++)
        for (int j = i+1; j < n-1; j++)
            ras += binsearch(j+1,n-1,bat[i]+bat[j]) - j;


    fout << ras;
    return 0;
}