Cod sursa(job #793886)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 4 octombrie 2012 16:44:10
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <cstdlib>

inline int comp(const void *a, const void* b){
    return *(int*)a-*(int*)b;
}

inline int nomorebs(const int* where, int minind, int maxind, const int what){
    while(maxind>=minind){
        int k=(maxind+minind)/2;
        if(where[k]>what) maxind=k-1;
        else if(k==maxind) return k;
        else if(where[k+1]>what) return k;
        else minind=k+1;
    }
    return -1;
}

int main(){
    std::ifstream fin("nrtri.in");
    std::ofstream fout("nrtri.out");
    int n;
    fin>>n;
    int *lung = new int[n];
    for(int i=0;i<n;i++) fin>>lung[i];
    std::qsort(lung,n,sizeof(int),comp);
    int count=0;
    for(int i=0;i<n-2;++i)
        for(int j=i+1;j<n-1;++j){
            int k=nomorebs(lung,j+1,n-1,lung[i]+lung[j]);
            if(k>j) count+=k-j;
        }
    fout<<count<<'\n';
    delete[] lung;
}