Cod sursa(job #1957402)

Utilizator deleted_2dbcc643895c1cb0DELETED deleted_2dbcc643895c1cb0 Data 7 aprilie 2017 15:38:24
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n,v[100000];
int cautbin (int x)
{
    int ls = 1,ld=n;
    int m, pozitie = 0;
    while (ls <=ld)
    {
        m = ls + (ld-ls)/2;
        if (v[m] <=x)
        {
            ls=m+1;
            pozitie = m;
        }
        else ld = m-1;
    }
    return pozitie;
}
int h(int x,int y)
{
    return cautbin(x) - cautbin(y-2);
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++) f >> v[i];
    sort (v+1,v+n+1);
    int ct=0;
    for  (int i=1; i<=n; i++)
        for (int j=i+1; j<=n-1; j++)
            ct+=h(v[i],v[j]);
    cout << ct;
    return 0;
}