Cod sursa(job #1552227)

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

using namespace std;

int v[100005];

int binarySearch(int x, int s, int n){
    int step = 1<<16;
    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-2;i++){
        for(j = i+1;j <= n-1;j++){
            poz1 = binarySearch(v[i]+v[j], j, n);
            poz2 = binarySearch(v[j]-v[i], j+1, n)+1;
            if(poz1 == n && (v[n] > v[i]+v[j])){
                continue;
            }
            ans = ans + (poz1-poz2+1);
        }
    }
    printf("%d",ans);
    return 0;
}