Cod sursa(job #1776261)

Utilizator MithrilBratu Andrei Mithril Data 11 octombrie 2016 08:49:55
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

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

inline bool isTriangle(vector<int> V, 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(vector<int> V, int left, int right, int best){
    if(left>right)
        return best;
    else{
        int m=(left+right)/2;
        if(isTriangle(V,i,j,m))
            return binSearch(V, m+1,right,m);
        else
            return binSearch(V, left,m-1,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.end());
    for(i=1;i<n-1;i+=1)
        for(j=i+1;j<n;j+=1){
            x = binSearch(V, j+1,n,0);
            if(x!=0)cnt+=x-(j+1)+1;
        }
    fout<<cnt;
    return 0;
}