Cod sursa(job #1776281)

Utilizator MithrilBratu Andrei Mithril Data 11 octombrie 2016 09:18:30
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;

int i,j,x,n;
long cnt;
vector<int> V;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

inline bool isTriangle(int a,int b,int c){
    if(V[a]+V[b]>=V[c]&&V[b]+V[c]>=V[a]&&V[c]+V[a]>=V[b])
        return true;
    else
        return false;
}

int binSearch(int left, int right){
    int best=0;
    while(left<=right){
        int m=(left+right)/2;
        if(isTriangle(i,j,m)){
            best=m;
            left=m+1;
        }
        else
            right=m-1;
    }
    return best;
}

int main()
{
    fin>>n;
    V.reserve(n+1);
    V[0]=-1;
    for(int i=1;i<=n;i+=1)fin>>V[i];
    sort(V.begin(),V.end());
    for(i=1;i<n-1;i+=1)
        for(j=i+1;j<n;j+=1){
            x = binSearch(j+1,n);
            if(x!=0)cnt+=x-(j+1)+1;
        }
    fout<<cnt;
    return 0;
}