Cod sursa(job #1503537)

Utilizator OFY4Ahmed Hamza Aydin OFY4 Data 16 octombrie 2015 14:11:55
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define nmax 807

int n,v[nmax];

int cautbin(int val){

    int start=0, step=(1<<10);

    for( ; step; step>>=1){

        int index=start+step;
        if(index>n)continue;
        if(v[index]<=val)start=index;
    }

    return start;
}

int main(){

    freopen("nrtri.in","r",stdin);
    //freopen("nrtri.out","w",stdout);

    scanf("%d", &n);

    int s=0;

    for(int i=1;i<=n;++i){

        scanf("%d", &v[i]);
    }

    sort(v+1,v+1+n);

    for(int i=1;i<=n-2;++i){

        for(int j=i+1;j<=n-1;++j){

            int k=v[i]+v[j];

            int a=cautbin(k)+1;

            if(v[a]>=k)++s;
        }
    }

    printf("%d \n", s);
}