Cod sursa(job #793884)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 4 octombrie 2012 16:28:04
Problema Numarare triunghiuri Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <cstdlib>

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

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 minind=j+1,maxind=n-1,k;
            bool found=false;
            for(;(!found)&&minind<=maxind;){
                k=(minind+maxind)/2;
                if(lung[k]>lung[i]+lung[j]) maxind=k-1;
                else if(lung[k+1]>lung[i]+lung[j]) found=true;
                else minind=k+1;
            }
            if(found&&k>j) count+=k-j;
        }
    fout<<count<<'\n';
    delete[] lung;
}