Cod sursa(job #1503551)

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

#define nmax 810

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+n+1);

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

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

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

            int a=cautbin(k);

            if(a==i || a==j)continue;

            if(v[a]+v[i]>=v[j] && v[a]+v[j]>=v[i] && v[i]+v[j]>=v[a])
            {
                ++s;
            }

        }
    }

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