Cod sursa(job #1494964)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 2 octombrie 2015 09:02:01
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int v[2001];
int verif( int a,int b,int c){
    if(a<b+c&&b<a+c&&c<a+b)
        return 0;
    else
        return 1;
}
int cautbin(int l1,int val,int l2){
    int mij,rasp=0;
    while(l1<=l2){
        mij=(l1+l2)/2;
        if(v[mij]<=val){
            l1=mij+1;
            rasp=mij;
        }
        else{
            l2=mij-1;
        }
    }
    return rasp;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("nrtri.in","r");
    fout=fopen("nrtri.out","w");
    int i,j,k,n,cate=0;
    fscanf(fin,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&v[i]);
    sort(v+1,v+n+1);
    for(i=n;i>=3;i--)
        for(j=i-1;j>=2;j--){
            k=cautbin(1,v[i]+v[j],j-1);
            while(k>=1){
                if(verif(v[i],v[j],v[k])==0)
                    (long long)cate++;
                k--;
            }
        }
    fprintf(fout,"%d",cate);
    fclose(fin);
    fclose(fout);
return 0;
}