Cod sursa(job #1552225)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 17 decembrie 2015 15:05:33
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

int v[100005];

int binarySearch(int x, int s, int n){
    int step;
    for(step = 1;step <= n;step <<= 1);
    for(s--;step;step >>= 1){
        if(s+step <= n && v[s+step] <= x){
            s += step;
        }
    }
    return s;
}

int main()
{
    int n,m,type,x,i,ans,j,poz1,poz2;
    int poz;
    freopen("nrtri.in", "r", stdin);// !!! nrtri !!!
    freopen("nrtri.out", "w", stdout);
    scanf("%d",&n);
    for(i = 1;i <= n;i++){
        scanf("%d",&v[i]);
    }
    sort(v+1,v+n+1);
    ans = 0;
    for(i = 1;i <= n;i++){
        for(j = i+1;j <= n;j++){
            poz1 = binarySearch(v[i]+v[j]+1, j+1, n);
            poz2 = binarySearch(v[j]-v[i], j+1, n)+1;
            ans = ans + (poz1-poz2+1);
        }
    }
    printf("%d",ans);
    return 0;
}