Cod sursa(job #1481585)

Utilizator CalinSpiridonSpiridon Calin CalinSpiridon Data 4 septembrie 2015 20:36:45
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int n,st,dr,mj,nr,p,k;
int a[810];

int caut(int d){
    st=0;
    dr=n+1;
    while((dr-st)>1){
        mj=(st+dr)/2;
        if(a[mj]<=d) st=mj;
        else dr=mj;
    }
    return st;

}

int main(){
    fin>>n;
    for(int i=1;i<=n;++i) fin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n-2;++i)
    for(int j=i+1;j<=n-1;++j){
            p=a[i]+a[j];
            if(p>=a[j+1]){
                k=caut(p);
                nr+=k-j;
            }
        }
    fout<<nr;

    return 0;
}