Cod sursa(job #1776273)

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

int i,j,x,n;
long cnt;
vector<int> V(801);
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[a]+V[c]>=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(left,right,best)){
            best=m;
            left=m+1;
        }
        else
            right=m-1;
    }
    return best;
}

int main()
{
    fin>>n;
    vector<int> V(n+1);
    V[0]=-1;
    for(int i=1;i<=n;i+=1)fin>>V[i];
    sort(V.begin(),V.begin()+n+1);
    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;
}